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

Đề tài: Quy Hoạch Động - Giải bài toán "Siêu thị may mắn" do đài truyền hình ZTV tổ chức

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

    Mặc định Quy Hoạch Động - Giải bài toán "Siêu thị may mắn" do đài truyền hình ZTV tổ chức

    Đây là 1 bài toán hay do mình sưu tầm được. Các bạn thử suy nghĩ xem sao. Trong vòng 1 tuần mình sẽ post lời giải lên nhé !
    (đề thi HSGQG năm nay).
    An được mời tham gia trò chơi "Siêu thị may mắn" do đài truyền hình ZTV tổ chức. Siêu thị được đặt trong trường quay truyền hình có n mặt hàng được đánh số từ 1 đến n và mặt hàng thứ i được niêm yết giá là Ci đồng i=1,2,...,n. Theo thể lệ của trò chơi, An được ban tổ chức tặng một thẻ mua hàng có giá trị là S đồng và phải dùng hết số tiền trong thẻ này để mua hàng trong siêu thị với điều kiện mặt hàng thứ i chỉ được mua với số lượng nhiều nhất là Mi (i=1,2,..n). An sẽ là người thắng cuộc nếu tìm được tổng số cách mua hàng thỏa mãn yêu cầu đặt ra và chỉ ra một cách mua hàng nếu có.
    Yêu cầu: hãy giúp An trở thành người thắng cuộc khi cho bạn biết trước các giá trị n, S, Ci, Mi (1<=n<=500, 1<=S<=10^5, 1<=Ci<=10^4,1<=Mi<=100) với i=1,2,...n.
    Dữ liệu vào
    - Dòng đầu: S,N;
    - Dòng i trong n dòng tiếp theo, mỗi dòng chứa Ci, Mi.
    Kết quả
    - Dòng đầu: d là tổng số cách mau hàng tìm được.
    - Nếu d>0 thì dòng thứ hai ghi một cách mua hàng tìm được là một dãy n số nguyên, trong đó số hạng thứ i là số lượng mặt hàng thứ i mua được trong cách này.
    Ví dụ:
    INPUT
    12 3
    4 1
    6 2
    2 1
    OUTPUT
    2
    0 2 0
    Hướng dẫn và gợi ý :
    - Đầu tiên để giải bài toán QHD ta phải cần tìm cơ sở quy hoạch. ( ở đây nếu không có món đồ nào thì số cách là 1 )
    - Bước thứ 2 là tìm công thức truy hồi dựa trên những điều kiện của bài toán. Ở đây ta để ý để mua được món đồ thứ i với giá C[i] thì số tiền lúc này sẽ bằng tổng số tiền của An - C[i]*M[i] ( M[i] là số lượng mua được của món hành thứ i ).
    - Gợi ý gọi F[i][j] là số cách mua được món hàng i với số lượng j cái. Nếu mua được món đồ thì F[i][j] = F[i][số tiền - M[i]*C[i]]....

  2. #2
    Ngày gia nhập
    08 2006
    Nơi ở
    Hải Phòng
    Bài viết
    218

    Bài này cũng hay đấy, để em làm thử xem sao.

    Bài này em cũng dùng quy hoạch động nhưng theo một công thức khác.
    Gọi f[i, j] là số cách mua hàng khi xét đến đồ vật thứ i và số tiền có là i.
    Nếu trong các cách mua không chọn vât i thì f[i, j]= f[i-1, j]
    Nếu trong các cách mua có chọn vật i thì f[i, j]= tổng( f[i, j- k*c[i] ) với k có giá trị từ 1 tới min ( m[i], j div c[i] )
    ==> f[i, j] = f[i-1, j] + tổng(.....)

    cơ sở quy hoạch động: f[i, 0] =1;


    Pascal Code:
    1. {$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q-,R-,S+,T-,V+,X+,Y+}
    2. {$M 16384,65520,655360}
    3. const
    4.       fi                        ='sieuthi.inp';
    5.       fo                        ='sieuthi.out';
    6.       maxn                      = 500;
    7.       maxs                      = 20000;
    8. type matrix                     = array[0..maxs] of integer;
    9. var
    10.    fh                           : text;
    11.    f1                           : matrix;
    12.    f2                           : ^matrix;
    13.    n, s                         : longint;
    14.    C, M                         : array[0..maxn] of integer;
    15. procedure input;
    16. var
    17.    i, j: longint;
    18.  
    19.   begin
    20.     assign(fh, fi); reset(fh);
    21.     readln(fh, s, n);
    22.     for i:=1 to n do
    23.       readln(fh, c[i], m[i]);
    24.     close(fh);
    25.   end;
    26. function min(a, b: longint): longint;
    27.   begin
    28.     if a> b then min:= b
    29.             else min:= a;
    30.   end;
    31.  
    32. procedure qhd;
    33. var
    34.    i, j, k, tong: longint;
    35.   begin
    36.     new(f2);
    37.     fillchar(f1, sizeof(f1), 0);
    38.     fillchar(f2^, sizeof(f2^), 0);
    39.     f1[0]:= 1;
    40.     for i:=1 to n do
    41.       begin
    42.         f2^:= f1;
    43.         fillchar(f1, sizeof(f1), 0);
    44.         for j:=s downto 0 do
    45.          begin
    46.            tong:= 0;
    47.            for k:= min(m[i], j div c[i]) downto 1 do
    48.              tong:= tong+ f2^[j- k* c[i]];
    49.            f1[j]:= tong + f2^[j];
    50.          end;
    51.       end;
    52.     dispose(f2);
    53.   end;
    54. procedure truyvet;
    55. var chon: array[1..maxn] of longint;
    56. procedure inkq;
    57. var i: longint;
    58.   begin
    59.     assign(fh, fo); rewrite(fh);
    60.     writeln(fh, f1[s]);
    61.     for i:=1 to n do
    62.       write(fh, chon[i],' ');
    63.     close(fh);
    64.     halt;
    65.   end;
    66. procedure try(i: longint; tong: longint);
    67. var j: longint;
    68.   begin
    69.     if i> n then
    70.       if tong=0 then inkq
    71.                 else
    72.     else
    73.       for j:=0 to min(m[i], tong div c[i]) do
    74.         begin
    75.           chon[i]:= j;
    76.           try(i+1, tong- j*c[i]);
    77.         end;
    78.   end;
    79. begin
    80.   try(1,s);
    81.   {chi xay ra neu khong tim thay ket qua}
    82.   assign(fh, fo); rewrite(fh);
    83.   writeln(fh, f1[s]);
    84.   writeln(fh,'Khong tim thay phuong an thoa man');
    85.  
    86.   close(fh);
    87. end;
    88. begin
    89.      input;
    90.      qhd;
    91.      truyvet;
    92. end.

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

    Bài này em cũng dùng quy hoạch động nhưng theo một công thức khác.
    Gọi f[i, j] là số cách mua hàng khi xét đến đồ vật thứ i và số tiền có là i.
    Hình như em nhầm chỗ này thì phải, phải là "đến đồ vật thứ i và số tiền có là j chứ nhỉ ?
    An sẽ là người thắng cuộc nếu tìm được tổng số cách mua hàng thỏa mãn yêu cầu đặt ra và chỉ ra một cách mua hàng nếu có.
    Hình như cái tìm min hơi thừa 1 tí nhỉ ? Đề bài chỉ yêu cầu tìm ra tổng số cách + 1 cách mua thôi mà phải không ?
    Nếu trong các cách mua có chọn vật i thì f[i, j]= tổng( f[i, j- k*c[i] ) với k có giá trị từ 1 tới min ( m[i], j div c[i] )
    ==> f[i, j] = f[i-1, j] + tổng(.....)
    Do em viết bằng Pascal, nên có 1 số chỗ anh không hiểu hết được ? Có gì cuối tuần anh sẽ coi lại kĩ hơn. Ý tưởng của em đúng rồi đấy nhưng anh chỉ không hiểu tại sao em lại chọn min ( m[i], j div c[i] ) ? Có thể anh hiểu sai ý em chỗ nào chăng ?
    Nhân tiện cho anh hỏi cái f2^ là con trỏ phải không, còn chỗ dispose(f2); có nghĩa là gì nhỉ ? new(f2); chỗ này là cấp phát động cho mãng f2 phải không em ?
    hixhix anh hỏi lung tung quá nhỉ !

  4. #4
    Ngày gia nhập
    10 2006
    Nơi ở
    Rừng Amazon
    Bài viết
    101

    Tôi chưa đọc kỹ code, mới chỉ đọc qua công thức quy hoạch nhưng cũng xin bày tỏ quan điểm của mình như sau:

    Công thức của chủ topic có vẻ không rõ ràng lắm, và tôi chưa nhìn thấy các điều kiện khác để kết thúc bài toàn. Ngày xưa những bài thế này tôi vẫn làm theo cách của hailoc.

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

    Ý em không phải là công thức hay cách sai, em chỉ nói là hình như Hailoc mắc lỗi quá cẩn thận thì phải, thường các đề bài QHD thường hay đi cùng với tìm max hoặc min của 1 giá trị nào đó, nhưng ở bài này thì đề bài chỉ yêu cầu tìm ra tổng số cách + 1 cách mua thôi mà phải không ?
    Còn công thức của em hình như sai thật~~ hix hix ! cám ơn anh đã nhắc nhở !
    phải là :
    F[i][0] = 1 (i = 1..n)
    F[i][j] = F[i][j] + F[i-1][j-C[i]*k] (j = 1..S, i =1..n, k=1..M[i])

    với F[i][j] là số cách mua được số tiền i với đồ vật thứ j !
    Đã được chỉnh sửa lần cuối bởi rox_rook : 22-10-2007 lúc 01:43 AM.

  6. #6
    Ngày gia nhập
    08 2006
    Nơi ở
    Hải Phòng
    Bài viết
    218

    Mặc định Quy Hoạch Động - Giải bài toán "Siêu thị may mắn" do đài truyền hình ZTV tổ chức

    với F[i][j] là số cách mua được số tiền i với đồ vật thứ j !
    Cái min(m[i], tong div c[i]) của em chính là để tính số cách mua được. Thông thường nếu không có dòng min trên thì phải cho j chạy từ 1 tới m[i] và phải có thêm lệnh kiểm tra if i- c[j]>=0.

    Mấy hôm nay em cũng tìm hiểu thêm về quy hoạch động và nhận thấy rằng. Quy hoạch động là phương pháp dùng để giải BÀI TOÁN TỐI ƯU nghĩa là tìm min hay max của một hàm nào đó. Trong cuốn giáo trình Tối ưu hoá có đưa ra 2 loại bài toán dùng quy hoạch động là
    1. Bài toán phân phối:
    Một tài nguyên có số lượng là a ( đơn vị ) và có N cách sử dụng tài nguyên đó. f(i, j) là hiệu quả đạt được khi dùng i tài nguyên theo cách thứ j. Hãy sử dụng lượng tài nguyên trên theo N cách sao cho hiệu quả cao nhất.
    --> giải bằng phương trình truy toán. (giống công thức trong bài tìm dãy con liên tiếp tăng dài nhất)
    2. Bài toán nhiều quá trình
    Nó mô tả tổng quát nhưng em xin lấy ví dụ ở bài toán vận chuyển. Cần vận chuyển hàng từ thành phối A đến thành phố B. Con đường vận chuyển dù đi theo cách nào cũng phải qua 4 thành phố. Đi từ thành phố nọ tới thành phố kia sẽ mất một chi phí nhất định. Hãy chọn ra con đường sao cho chi phí là nhỏ nhất.
    --> Cái này dùng phương trình hàm để giải ( giống bài tính tích ma trận )

    Còn một số bài toán như bài siêu thị này, tuy người ta vẫn đề là phương pháp quy hoạch động nhưng em thấy nói như vậy là sai. Đó là thuộc bài toán đếm nâng cao, dùng công thức truy hồi để tìm ra kết quả.

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

    Anh hiểu ý em rồi ! Do đọc ẩu chỉ nên không nhận ra cái hàm min của em ! Sorry em nhé!
    Như HaiLoc đã trình bài thì bài này thuộc dạng bài toán đếm dùng công thức truy hồi truy hồi để giải. Mình sẽ post cách giải của bài này theo 1 hướng khác cho các bạn tham khảo thêm.

    Đầu tiên ta thấy công thức truy hồi trên :
    F[i][0] = 1 (i = 1..n)
    F[i][j] = F[i][j] + F[i-1][j-C[i]*k] (j = 1..S, i =1..n, k=1..M[i])

    Ta để ý thực ra nó dùng hàng thứ i tính vào dòng i-1 cho nên để tiết kiêm không gian ta chỉ cần dùng mãng 1 là đủ :
    với cơ sở : F[0] = 1;
    và công thức truy hồi đơn giản như sau : F[i] = F[i] + F[i-C[j]*k]

    C++ Code:
    1. #include <iostream>
    2. #include <iomanip>
    3.  
    4. using namespace std;
    5. const int maxx = 100;
    6.  
    7. int productValue[maxx];      /*Product value*/
    8. int productQuantity[maxx];      /*Maximum quantiy of product can get*/
    9. int matrixSolution[maxx];       /*Solution Board*/
    10.  
    11. int totalMoneyofUser;       /*Value of Gift Card*/
    12. int PRODUCTs;             /*Total of product*/
    13. int quantity[maxx], type[maxx];
    14.  
    15. void ReadInputFromUser()
    16. {
    17.     cout << "Enter the number of product : ";
    18.     cin >> PRODUCTs;
    19.     cout << "Enter gift-card's value $$$ : " ;
    20.     cin >> totalMoneyofUser;
    21.  
    22.     for ( int i = 1; i <= PRODUCTs; i++ )
    23.     {
    24.         cout << "The product [" << i << "]'s value : ";
    25.         cin >> productValue[i];
    26.         cout << "The maximum items you can get : ";
    27.         cin >> productQuantity[i];
    28.     }
    29.     matrixSolution[0] = 1; /*Base for recursive formula*/
    30. }
    31.  
    32. void DynamicProgrammingProcedure()
    33. {
    34.     for(int j = 1; j <= PRODUCTs; j++)
    35.     {
    36.         for(int i = totalMoneyofUser; i >= 1; i--)
    37.         {
    38.             for(int k = 1; k <= productQuantity[j]; k++)
    39.             {
    40.                 matrixSolution[i] = matrixSolution[i] + matrixSolution[i-productValue[j]*k];
    41.                 if(matrixSolution[i] == matrixSolution[i-productValue[j]*k]) /*Base for Trace() function )*/
    42.                 {
    43.                     type[i] = j;
    44.                     quantity[i] = k;
    45.                 }
    46.             }
    47.         }
    48.     }        
    49. }
    50.  
    51. void Trace(int S)
    52. {
    53.     if(matrixSolution[totalMoneyofUser] == 0)
    54.     {
    55.         cout << "No way!!!\n\n";
    56.     }
    57.     else
    58.     {
    59.         cout << "-----------------\n\n\n";
    60.         do
    61.         {
    62.             cout << "Type of Product : " << type[S] << endl;
    63.             cout << "Quantities : " << quantity[S] << endl;
    64.            
    65.             S = S - productValue[type[S]]*quantity[S];
    66.         }while(S != 0);
    67.     }
    68. }
    69.  
    70. int main()
    71. {
    72.     ReadInputFromUser();
    73.     DynamicProgrammingProcedure();
    74.     Trace(totalMoneyofUser);
    75.          
    76.     return 0;
    77. }
    Đã được chỉnh sửa lần cuối bởi rox_rook : 02-03-2008 lúc 02:57 AM.

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

    Vậy độ phức tạp của bài này là bao nhiêu giúp mình với nhé.có phương trình đệ quy nữa thì càng tốt

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

  1. nghĩa của 3 từ "principals", "artifacts", "securables" là như thế nào?
    Gửi bởi ntbao trong diễn đàn English for IT | Tiếng anh cho dân CNTT
    Trả lời: 1
    Bài viết cuối: 29-09-2012, 11:29 AM
  2. Problems : " recover tree " with input as " preorder" and "inorder"
    Gửi bởi HoangManhHa1991 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 16
    Bài viết cuối: 13-04-2011, 10:19 PM
  3. Kỹ thuật C++ Toán tử thao tác bit.. "&"(và bit), "|"(hay bit), "^"(hoặc bit). là gì!
    Gửi bởi quan_pc trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 11
    Bài viết cuối: 20-02-2011, 08:05 PM
  4. "Cơ chế hoạt động gửi nhận Web (Http)". Giúp mình tìm hiểu
    Gửi bởi HappyBunny trong diễn đàn Thắc mắc chung
    Trả lời: 1
    Bài viết cuối: 01-06-2010, 09:54 AM
  5. Đề xuất Thêm flag "Đã giải quyết" (Resolved) hay "chưa giải quyết" cho topic
    Gửi bởi cuonchagio trong diễn đàn Ý kiến, đề xuất và khiếu nại
    Trả lời: 3
    Bài viết cuối: 28-01-2010, 05:34 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