Bài toán cái túi (xếp ba lô – knapsack) trong Pascal

57
Lập trình Pascal

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.