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

Đề tài: Ngân hàng trả tiền.

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

    Mặc định Ngân hàng trả tiền.

    Xin lỗi các mod tui post bài "trùng", post bên bài tập C++ trả lời ít quá, hy vọng đem qua đây sẽ có nhiều người góp ý.
    Mong giúp tìm thuật toán giải cái câu kia. Tui lâp trình chuối quá nghĩ hoài ko ra cách gì cả.


    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 đây thì chạy 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.
    Code tính tiền của tui. Bỏ vô mảng thì chẳng biết viết như thế nào nữa cả nên viết riêng vài cái như vậy.
    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;}

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

    Bạn đọc thêm về "Quy hoạch tuyến tính" nhé. Bài này khác hẳn bài "Cái túi" đấy, áp dụng bài toán "Cái túi" chỉ là một Heuristic thôi.

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

    Bài này hôm bữa, có đứa bạn cùng quê hỏi, tôi nói qua đây, không ngờ cậu cũng quan tâm.
    Thiệt cũng muốn giúp, nhưng ngoài greedy ra, tôi ko biết làm sao nữa cả. Để R2 rãnh rang lão giúp xem sao. alg tôi dốt quá :(

  4. #4
    Ngày gia nhập
    01 2008
    Bài viết
    240

    Trích dẫn Nguyên bản được gửi bởi PDV Xem bài viết
    Xin lỗi các mod tui post bài "trùng", post bên bài tập C++ trả lời ít quá, hy vọng đem qua đây sẽ có nhiều người góp ý.
    Mong giúp tìm thuật toán giải cái câu kia. Tui lâp trình chuối quá nghĩ hoài ko ra cách gì cả.


    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 đây thì chạy 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.
    Code tính tiền của tui. Bỏ vô mảng thì chẳng biết viết như thế nào nữa cả nên viết riêng vài cái như vậy.
    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;}
    Cái này có thể chơi quý hoạch động được đó
    Time

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

  1. Trao đổi liên kết, trao doi logo, Text Link với các webforumblog (free)
    Gửi bởi nguyenlam14990 trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 31
    Bài viết cuối: 13-03-2012, 11:53 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