Bài toán. Trong siêu thị có n gói hàng đánh số từ 1 đến n (n≤1000), gói hàng thứ i có trọng lượng Wi ≤1000 và giá trị Vi ≤1000. Một tên trộm đột nhập vào siêu thị mang theo một cái túi có thể mang được tối đa trọng lượng M ≤1000. Hỏi tên trộm sẽ lấy đi những gói hàng nào để được tổng giá trị lớn nhất?
Dữ liệu vào: Cho từ file văn bản BAG.INP
- Dòng đầu chứa hai số nguyên dương n, M
- n dòng tiếp theo, dòng thứ i ghi hai số nguyên dương Wi và Vi .
Kết quả: Ghi ra file văn bản BAG.OUT
- Dòng đầu ghi giá trị lớn nhất tên trộm có thể lấy được.
- Dòng thứ hai ghi chỉ số của những gói hàng bị lấy theo thứ tự chỉ số từ nhỏ đến lớn.
Ví dụ:
|
BAG.INP |
BAG.OUT |
|
5 11 3 3 4 4 5 4 9 10 4 4 |
11 1 2 5 |
Const fin ='BAG.INP';
fout='BAG.OUT';
Var W,V:array[1..1000] of Integer;
T:array[0..1000,0..1000] of Longint;
n,m,i,j,max:Longint;
f:Text;
Begin
Assign(f,fin);
Reset(f);
Readln(f,n,m);
For i:=1 to n do Readln(f,W[i],V[i]);
Close(f);
For i:=1 to n do
For j:=1 to M do
Begin
max:=T[i-1,j];
If j>=W[i] then
If max<T[i-1,j-W[i]] + V[i] then max:=T[i-1,j-W[i]] +V[i];
T[i,j]:=max;
End;
Assign(f,fout);
Rewrite(f);
Writeln(f,T[n,M]);
j:=M;
For i:=n downto 1 do
If T[i,j]<>T[i-1,j] then
Begin
V[i]:=0;
j:=j-W[i];
End;
For i:=1 to n do
If V[i]=0 then Write(f,i,' ');
Close(f);
End.