Từ 1 tới 8 trên tổng số 8 kết quả

Đề tài: bài toán đổi tiền dùng giải thuật tham lam và nhánh cận

  1. #1
    Ngày gia nhập
    10 2008
    Bài viết
    3

    Mặc định bài toán đổi tiền dùng giải thuật tham lam và nhánh cận

    Mình có bài toán sau,mong các anh chị và các bạn giúp mình với.Cảm ơn nhiều
    Câu 1 mình dùng giải thuật tham lam nhưng không tối ưu
    câu 2 mình định dùng phương pháp nhánh cận

    * Một quầy trả tiền có N loại tiền với các mệnh giá (giá trị tiền ghi trên tờ tiền ) là A[1], A[2], ….A[N] ( Các A[i] là nguyên dương và khác nhau từng đôi). Giả thiết loại tiền mệnh giá A[i] có B[i] tờ (1 i N). Có M khách ( được đánh số hiệu từ 1 đến M ) cần lấy tiền. Số tiền khách j cần lấy là K[j], K[j] nguyên dương, 1 j M). Quy định rằng với mỗi khách hoặc quầy từ chối chưa trả tiền hoặc quầy phải trả đúng số tiền mà khách cần lấy.Dữ liệu vào được cho trong file văn bản có tên INP.TXT trong đó dòng đầu ghi giá trị N (N 10), dòng tiếp theo ghi các giá trị A[1], A[2], ….A[N], dòng tiếp theo ghi các giá trị B[1], B[2], ….B[N], sau đó là dòng ghi giá trị M (M 20), cuối cùng là dòng ghi các giá trị K[1], K[2], ….K[M], tất cả các giá trị đều nguyên dương.


    1. Tìm cách trả tiền sao cho trả được nhiều khách nhất. Thông báo kết quả ra file văn bản với tên OUT2.TXT trong đó dòng đầu ghi số khách được trả tiền, trong các dòng tiếp theo, mỗi dòng ghi thông tin về một khách được trả tiền gồm số hiệu của khách, số tiền phải trả và dãy các số X[1], X[2],…..X[N], trong đó X[i] là số tờ của loại tiền mệnh giá A[i], 1 i N, được trả cho khách.

    2. Tìm cách trả tiền sao cho trả được nhiều tiền nhất. Thông báo kết quả ra file văn bản với tên OUT3.TXT trong đó dòng đầu ghi tổng số tiền đã trả được, trong các dòng tiếp theo, mỗi dòng ghi thông tin về một khách được trả tiền theo quy cách giống câu 1


    Lưu ý không post các câu hỏi vào Box Hướng dẫn. Lần sau vi phạm sẽ xóa.
    Đã được chỉnh sửa lần cuối bởi zkday2686 : 26-10-2008 lúc 11:55 PM.

  2. #2
    Ngày gia nhập
    10 2006
    Nơi ở
    In Your Bugs
    Bài viết
    823

    Bài này nhe VuHP nói dùng greedy.
    Kid không rành vụ giải thuật này lắm nhưng nếu dùng thuật toán tham thứ tự ( tăng/ giảm ) dần của K[] thì có ổn ko ?

    Ví dụ câu này :

    1. Tìm cách trả tiền sao cho trả được nhiều khách nhất. Thông báo kết quả ra file văn bản với tên OUT2.TXT trong đó dòng đầu ghi số khách được trả tiền, trong các dòng tiếp theo, mỗi dòng ghi thông tin về một khách được trả tiền gồm số hiệu của khách, số tiền phải trả và dãy các số X[1], X[2],…..X[N], trong đó X[i] là số tờ của loại tiền mệnh giá A[i], 1 i N, được trả cho khách.

    Nếu ta sắp xếp theo chiều tăng của giá trị tiền mà khách thứ j cần lấy, thì tổng số khách mà chúng ta có thể trả được sẽ là lớn nhất ( do tổng số tiền là nhỏ nhất ) Chúng ta sẽ greedy trên mảng giá trị này, kết hợp với việc phân phối số tiền hợp lí ( Tiền thứ i có B[i] tờ ) thì liệu tạo ra kq tối ưu ko ?

    Nếu câu 1 tối ưu, thì câu 2 cũng có thể làm được theo cách này đúng ko ta ?

    R2 đâu rồi, đúng sở trường của cậu rồi đó.

    Để trả được nhiều khách nhất, thì chúng ta có thể sắp xếp mảng

    Bài này hay thật, nhưng kid vẫn không tìm ra kq tối ưu. Ước gì có bác bete, cậu HaiLoc và R2 cùng xúm lại chỉ giáo xem sao ?

    # VHP: Cậu send cái code greedy lên tôi built thử nhé.

    : Bài này nếu cậu dùng nhánh cận, thì làm sao cậu quyết định cắt một nhánh ? Ko hiểu ý cậu lắm.

  3. #3
    Ngày gia nhập
    10 2008
    Bài viết
    3

    Câu 2 xuất phát ý tưởng từ bài toán cái túi: có n đồ vật,mỗi đồ vật có khối lượng wi,giá trị bi(i=1,n) và 1 cái túi có trọng lượng c.Yêu cầu là tìm cách cho các đồ vật vào túi sao cho giá trị của túi là max.
    Bài toán này có nhiều cách giải.Có thể dùng nhánh cận hoặc quy hoạch động
    .Nhưng mình không biết vận dụng vào câu 2 của bài này.
    Mong các anh chị chỉ giúp!
    .

  4. #4
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    - Bài 1 dùng QHD nhanh hơn, nhánh cận cũng ok nhưng chạy chậm lắm.
    - Cậu chỉ cần suy ra 1 công thức truy hồi là xong ngay thôi. Bây giờ thì không có thời gian giúp cậu vả lại cũng lâu lắm rồi không làm QHD, nên có làm thì tui cũng phải suy nghĩ như cậu thôi. Hơn nữa bây giờ cũng chẳng có compiler T_T.
    - Điều duy nhất tui có thể giúp cậu lúc này là cậu code thử, mai lên trường tui sẽ test thử xem sao.
    - Greedy không thể dùng trong bài 1 được.
    @ kid : xúi bậy hoài nha T_T, đang thi mà cứ châm dầu vào lửa hoài b-( ! Ông đang rảnh thì giúp đi, phá quá b-( !

  5. #5
    Ngày gia nhập
    10 2006
    Nơi ở
    In Your Bugs
    Bài viết
    823

    @R2: hix, rãnh đâu, kid năm III rùi. Phải làm đồ án môn học nữa. Mà R2 này, chả biết bên đất Mỹ xa xôi, các cậu học giáo trình như thế nào nhỉ ? Hồi trước anh Huy Nguyên có send giáo trình trường WS thấy cũng hay hay. Có gì cậu viết ym cho tớ

    @VHP: Nếu bài này cậu dùng quy hoạnh động thì phải tìm ra công thức truy hồi + CM. Liệu cậu đã có nó chưa ?

    Mấy bài này thường dành cho các bác gà chọi ? Nếu cậu cũng là gà chọi, thì nên hỏi giáo viên hướng dẫn

    Bài này hay lắm, có gì cậu send code tôi tham khảo với nhé Thanks ( hoặc í của cậu cũng được, tôi built rồi viết lại hàm find, chứ code từ đầu oải lắm )

    Edit:

    Bài này khác bài cái túi, vì số tiền K[] không chỉ nhỏ hơn tổng số tiền còn lại mà còn phải kiểm tra xem có trả được hay không

    vd Tiền A[0] = 10K, có B[0] = 10;
    vậy tổng số tiền còn lại là 100K
    Nhưng K[i] cần 59K -> Không trả được.
    Đã được chỉnh sửa lần cuối bởi kidkid : 29-10-2008 lúc 11:57 AM.

  6. #6
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Mặc định bài toán đổi tiền dùng giải thuật tham lam và nhánh cận

    - Chài, mấy bài này cơ bản thôi mà kid, nếu trong trường đang dạy QHD thì cho mấy bài này là quá phù hợp rồi !
    - Cứ làm QHD là nhớ sách của thầy Hoàng ! Tìm sách của Lê Minh Hoàng đọc tới đọc lui các bài QHD là cậu làm bài trên 1 phát 1 !
    - Còn muốn gà chọi thì lên Topcoder hay ACM mà chọi T_T, ná thở luôn chứ chọi T_T !

  7. #7
    Ngày gia nhập
    10 2008
    Bài viết
    3

    re:kidkid

    Câu 1,đầu tiên mình loại những k[j] không có khả năng chi trả,bằng cách :T=k[j]%min a[i],t!=0,loại thằng k[i] ra khỏi danh sách có khả năng trả.

  8. #8
    Ngày gia nhập
    10 2006
    Nơi ở
    In Your Bugs
    Bài viết
    823

    @VHP:
    Có thắc mắc thế này :
    K[0] = 11;
    A[0] = 3;
    A[1] = 5;

    Nếu theo cậu thì loại thế nào ? ( Min(A) -> A[0] K[j]%3 = 2 != 0 -> loại A[0] ? )

    @R2: Uh, mấy bài toán trong sách thầy Hoàng thì kid có vọc nhưng bài này thấy bí bí chỗ chọn tiền đổi.

    Vd: Tiền K[j] = 11 Có các cách đổi sau :

    3 + 3 + 5;
    5 + 5 + 1;
    2 + 3 + 6;
    ... ... ...
    Nếu chọn đổi cho K[j] là cách thứ i trong những cách trên.
    Thì tại K[j+n] sẽ không thể đỏi dù số tiền còn lại lớn hơn.
    Nhưng nếu ta chọn K[j] là cách thứ t. Thì K[j+n] lại đổi được.

    Vậy chọn thế nào ?
    Kid nghĩ là cứ chọn trả theo tiền có mệnh giá lớn nhất ( ưu tiên sao cho mệnh giá này có thể chia hết cho các mệnh giá còn lại ).
    Nếu đến lúc cuối cùng, khi không thể trả tiền cho khách được nữa mà số tiền còn lại lớn hơn số tiền ( nhỏ nhất ) cần trả thì tìm cách thay đổi các mệnh giá đã đổi trước đó sao cho có thể trả được cho vị khách hiện tại.


    R2 bỏ chút thời gian ra suy nghĩ tí nhé, kid không rành alg lắm.

Các đề tài tương tự

  1. Bài tập C Bài tập tính lãi ngân hàng dùng đệ quy hoặc tham chiếu, tham trị
    Gửi bởi thaohoangf trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 2
    Bài viết cuối: 08-10-2012, 08:24 AM
  2. Tô Màu theo thuật giải tham lam (Trí tuệ nhân tạo)
    Gửi bởi thienthanit trong diễn đàn Thủ thuật, Tutorials CTDL & Giải thuật
    Trả lời: 8
    Bài viết cuối: 25-02-2012, 07:04 PM
  3. giải thuật tham ăn bài toán nhặt bắp
    Gửi bởi thantai2000 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 0
    Bài viết cuối: 24-12-2010, 12:58 PM
  4. Tìm đường đi ngắn nhất bằng giải thuật tham lam?
    Gửi bởi Jindo trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 2
    Bài viết cuối: 13-10-2010, 01:00 PM
  5. cho hỏi về cách dùng Tham biến và tham trị trong C++
    Gửi bởi dta4c trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 2
    Bài viết cuối: 12-01-2008, 10:18 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn