Thread: Bài tập hay ! Bạn sẽ là người nhanh nhất ??

Khi gặp một vấn đề thú vị, làm sao ta có thể đành lòng xếp xó nó với một thuật giải vớ vẩn ?

"Cây khế nhà Khánh rất sai quả nên có một con chim to to đến ăn. Ăn xong, chim chở Khánh ra đảo để trả công bằng vàng. Đảo có N cục vàng. Anh ấy muốn chuyển hết cả N cục vàng của mình về nhà. Nhưng khổ nổi các cục vàng này lại có trọng lượng và kích thước khổng lồ. Khánh đem theo một cái túi ba trăm gang to đùng nhưng vẫn chưa chắc chứa hết đống vàng này. Khổ quá đi! Lấy cục nào, bỏ cục nào bây giờ! Các bạn giúp anh ấy tìm ra một cách chọn vàng để thu được giá trị lớn nhất mà vẫn không làm rách túi đi.

Input
Dòng 1: Chứa 2 số nguyên: số cục vàng N (1 ≤ N ≤ 40) và tải trọng tối đa của túi M (1 ≤ M ≤ 109).
N dòng sau: Mỗi dòng chứa 2 số nguyên: trọng lượng Wi và giá trị Vi của cục vàng thứ i (1 ≤ Wi, Vi ≤ 108).

Output
Một số nguyên duy nhất là giá trị lớn nhất thu được.
Example
Input:
3 4
1 4
2 5
3 6

Output:
10

Giới hạn thời gian: 3s"

Chơi một trò chơi nào ?

Bài này là bài toán cái túi mà, không cần giới hạn đến 3s đâu anh leon ah`,

Spoiler:

PHP Code:

program Vang;
uses crt;
const fi = '';
      fo = '';
var W,V: array[1..40] of byte;
    n,m: byte;
    F: array[0..40,0..200] of word;
    g: text;

procedure Input;
var i: byte;
begin
  assign(g,fi);
  reset(g);
  readln(g,n,m);
  for i:= 1 to n do readln(g,W[i],V[i]);
  close(g);
end;

procedure optimize;
var i,j: byte;
begin
  for j:= 1 to m do F[0,j]:= 0;
  for j:= 1 to m do If W[1] <= j then F[1,j]:= V[1] else F[1,j]:= 0;
  for i:= 2 to n do
   for j:= 1 to m do
    begin
     F[i,j]:= F[i-1,j];
     If (W[i] <= j) and (F[i,j] < F[i-1,j-W[i]]+V[i]) then
      F[i,j]:= F[i-1,j-W[i]]+V[i];
    end;
end;

procedure Output;
begin
  assign(g,fo);
  rewrite(g);
  Writeln(g,F[n,m]);
  close(g);
end;

BEGIN
  clrscr;
  Input;
  optimize;
  Output;
  readln;
END. 


@WaoRuby: Chú không hiểu ẩn ý của anh Leon rồi

Khi gặp một vấn đề thú vị, làm sao ta có thể đành lòng xếp xó nó với một thuật giải vớ vẩn ?