Trang 1 trên tổng số 2 12 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 11 kết quả

Đề tài: Bài toán trả tiền cho nhiều khách nhất.

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

    Mặc định Bài toán trả tiền cho nhiều khách nhất.

    Nói sơ qua đề bài nhé:
    //---------------------------------------------------------------------------
    Có N loại tiền mệnh giá A[i] (1<= i <=N) loại A[i] có B[i] tờ.
    Có M khách đến rút tiền (như rút ATM ấy) số tiền khách cần lấy là K[j] (1<=j<=M), số tờ tiền loại A[i] phải trả cho khách là X[i].
    Yêu cầu:
    Tìm cách trả tiền sao cho trả được nhiều khách nhất. Phải trả đúng số tiền khách yêu cầu (rút ATM ai lại đem thối lại đâu ) hoặc không trả, bỏ qua khách đó.
    //---------------------------------------------------------------------------
    Ý tưởng của tui:
    - Xếp K[j] (số tiền khách cần lấy) từ nhỏ đến lớn.
    - Xếp A[i] (mệnh giá tiền) từ lớn đến nhỏ.
    - Duyệt từng khách
    + Số tờ tiền phải trả ban đầu bằng 0, nhân với mệnh giá lớn nhất, tăng 1 số tờ tiền, tiếp tục quay lại nhân, đến khi nào không thể nhân thêm được nữa (nếu nhân tiếp thì số tiền trả bây giờ lớn hơn K[j]-số tiền khách j cần lấy) ta xét đến laọi tiền mệnh giá lớn thứ hai, cứ tiếp tục như vậy đến hết tất cả mệnh giá tiền nếu như nó bằng đúng số tiền khách cần lấy thì ok, được 1 khách rồi, nếu không đúng bằng K[j] thì bỏ qua khách đó, xét tiếp khách j+1.
    + Làm đến khi nào hết tiền, hết khách.
    - Xuất lại số tờ tiền X[i] đã trả.
    //---------------------------------------------------------------------------
    => Không biết thuật toán làm như thế có được không? Mà tui thấy chỗ lấy mệnh giá lớn nhất nhân với số tờ tăng dần ấy cũng có gì đó không ổn lắm.
    => Nếu được xin "hiến kế" cho tui thuật toán nào tốt hơn.
    => Nghĩ thế mà tui viết hoài không được, cứ sai lên sai xuống lặp lung tung hết trơn, trình độ hơi chuối.
    => Mọi người có thể hướng dẫn giúp tui được không?
    //---------------------------------------------------------------------------
    Thanks!
    Đã được chỉnh sửa lần cuối bởi PDV : 25-10-2008 lúc 03:33 PM.

  2. #2
    Ngày gia nhập
    04 2008
    Bài viết
    244

    trả đựoc cho nhiều khách nhất là sao mình khôgn hiểu,nếu có 1 số tiền nhất định thì chỉ có thể trả cho 1 số người nhất định-> nếu thế cứ lựa thằng nào đòi rút 1 đồng thì trả( mệnh ja bé nhất ) thế là sẽ được nhiều nhất

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

    Trích dẫn Nguyên bản được gửi bởi honey Xem bài viết
    trả đựoc cho nhiều khách nhất là sao mình khôgn hiểu,nếu có 1 số tiền nhất định thì chỉ có thể trả cho 1 số người nhất định-> nếu thế cứ lựa thằng nào đòi rút 1 đồng thì trả( mệnh ja bé nhất ) thế là sẽ được nhiều nhất
    Có một số lương khách và tiền nhất định, nhưng nếu bạn trả ko đúng cách sẽ gặp tình trạng số tiền trả ko đúng bằng sô tiền khách cần lấy.
    Tui cũng làm thế, thằng nào nhỏ nhất tui trả trước, tiếp tục đến thằng lớn hơn.
    Đã được chỉnh sửa lần cuối bởi PDV : 25-10-2008 lúc 04:04 PM.

  4. #4
    Ngày gia nhập
    10 2008
    Nơi ở
    Hà Nội
    Bài viết
    49

    Ý ông bạn là nếu trả random lung tung thì sợ những người sau lấy tiền sẽ ko còn số tiền mệnh giá phù hợp chứ j (VD: Còn 2 triệu toàn tờ 500k, khách muốn lấy 800k thì ko trả đc chứ ji?)
    Tui nghĩ là trả hết tiền mệnh giá to trước, khớp với số tiền thằng nào thì cứ trả thằng đó. Còn lại để dành tiền lẻ đấy. Thằng lấy tiền sau gắng chịu tiền lẻ.
    (Tiền lẻ hay tiêu, tiêu nhiều hết sớm -> rút tiếp he he)

  5. #5
    Ngày gia nhập
    05 2008
    Bài viết
    24

    Có thuật toán nào để trả tiền không? Tui viết rồi nhưng thấy nó chuối quá có cách nào hay hơn, tối ưu hơn không??? Code tui như sau:
    Giả sử tiền trả = tientra, có 5 mệnh giá: từ 20000 đến 5000
    Code:
    for(int i=0;i<=tientra/20000)
    
    for(int j=0;j<=(tientra-i*20000)/10000;j++)
    for (int l=0;l<=(tientra-i*20000-j*10000)/5000)
    if((i*2000+j*10000+l*5000)=tientra)
    {printf("%d %d %d",i,j,l);break;}
    Viết như thế này lỡ đâu sau này lạm phát, có thêm nhiều loại tiền mệnh giá khác nữa hoặc như bây giờ có 10 loại thì viết ct rụng tay luôn, vả lại nếu nhiều hơn thì lâu hơn(lặp cả một mớ). Thuật toán trên chắc là chạy (hy vọng thế-vì nó chỉ mới là ý tưởng nhất thời của tui thôi nhưng mà xem ra thấy mờ mịt chẳng có cái nào khác nữa). Mong anh em góp ý. Thanks!

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

    Mặc định Bài toán trả tiền cho nhiều khách nhất.

    bài này mình thấy na ná loại bài xếp hộp vào ba lô; mình đang làm bài tập về cái này, ai có ý kiến hay ság kiến gì thì nói luôn nhé

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

    Đúng bài bên box GiaiTHuat. QUa đó thảo luận luôn đi bạn

  8. #8
    Ngày gia nhập
    06 2008
    Bài viết
    25

    Đề ghi ko rõ gì cả, mình ghi lại như vầy thử đúng chưa nhá

    Có N loại tiền mệnh giá A[i] (1<= i <=N) loại A[i] có B[i] tờ.
    Có M khách đến rút tiền (như rút ATM ấy) số tiền khách cần lấy là K[j] (1<=j<=M), số tờ tiền loại A[i] phải trả cho khách là X[i].
    Có N loại tiền, đánh số là loại 1, 2, ... N. Loại thứ i (1 <= i <= N) có mệnh giá A[i] và có tất cả B[i] tờ trong máy.
    Có M khách, đánh số là 1, 2, 3... M. Khách thứ j (1 <= j <= M) cần rút số tiền là K[j], và phải là loại tiền X[j].

    Như trên fải ko? Nếu fải chắc là đề bài sai rồi.

  9. #9
    Ngày gia nhập
    05 2008
    Bài viết
    24

    Sác, nguyên văn đề như sau:
    Ngân hàng có N loại tiền, mệnh giá là A[1]...A[N]. Giả thiết loại A[i] có B[i] tờ (1<=i<=N). Có M khách đến rút tiền. Số tiền khách cần lấy là K[j] (1<=j<=M). Ngân hàng hàng cso quyền từ chối trả tiền hoặc trả đúng (lưu ý cái trả đúng vì sau này đó là căn cứ để loại bớt khách) số tiền khách cần lấy. Đọc file dữ liệu vào theo thứ tự các dòng mỗi dòng một giá trị:N,A[i],B[i],M,K[j] (cái này viết rồi chỉ có chưa biết cách nào tính số khách thôi.)
    1. Tìm cách trả tiền nhiều khách nhất. In ra Số khách được trả tiền (vì sẽ có một số khách tiền bị "lẻ"-ngân hàng ko có ĐÚNG số tiền khách lấy), Số thứ tự khách (cái này gọi là Mã khách hàng cho nó pro, hehe), Số tiền phải trả (tổng tiền trả lấy số tiền phải trả cho từng khách cộng lại, vì có thể ko trả tiền cho khách nên phải in ra cái này), dãy các số X[i]( X[i] là số tờ tiền mệnh giá A[i] trả cho khác ở trên)
    2. Tìm cách tả tiền sao cho được nhiều tiền nhất. Xuất câu trên. (Cách làm thì chắc cũng y vậy.)

    Không áp dụng nguyên bài toán cái túi, hoặc dùng thuật toán nhánh cận đề lấy tối ưu được vì các bài toán đỏ chỉ lấy 1 thứ thôi còn bài này lấy cả mớ tờ tiền. Còn tham lam lúc đúng lúc ko, cái tính tiền tui viết bênh trên thì chỵ mệt nghỉ luôn, cả một đóng vòng lặp. Nhìn có vẻ đơn giản mà sao "đâu cái đàu" quá. Mọi người ai có ý tưởng gì không vậy.
    Đã được chỉnh sửa lần cuối bởi PDV : 31-10-2008 lúc 09:52 AM.

  10. #10
    Ngày gia nhập
    12 2007
    Bài viết
    22

    mình thấy bài này cũng khá hay đấy chứ! Mong rằng có pro nào giúp....!

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

  1. Nhập liệu vào textbox trong C#, trả về nhiều kết quả?
    Gửi bởi theduong trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 8
    Bài viết cuối: 11-12-2012, 07:38 AM
  2. Cách nhập nhiều ma trận từ 1 file text trong C?
    Gửi bởi churrym 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: 11-04-2011, 09:42 PM
  3. Lập trình C++: Nhập nhiều ma trận từ 1 file??
    Gửi bởi trankieu90 trong diễn đàn Thắc mắc lập trình Visual C++
    Trả lời: 7
    Bài viết cuối: 03-04-2011, 11:47 AM
  4. Tìm cột có số chẵn nhiều nhất trong ma trận
    Gửi bởi hoahoctro207 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 13
    Bài viết cuối: 16-01-2011, 08:50 AM
  5. website cập nhật nhiều laptop mới và hot nhất, bán trả góp thủ tục đơn giản
    Gửi bởi diemnt trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 0
    Bài viết cuối: 02-07-2010, 03:23 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