Giải thuật và lập trình: §3.2. Bài toán cái túi

Trong siêu thị có n gói hàng (n <= 100), gói hàng thứ i có trọng lượng là W_i <= 100 và trị giá V_i <= 100. Một tên trộm đột nhập vào siêu thị, tên trộm mang theo một cái túi có thể mang được tối đa trọng lượng M ( M <= 100). 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.

Input: file văn bản BAG.INP

• Dòng 1: Chứa hai số n, M cách nhau ít nhất một dấu cách
• n dòng tiếp theo, dòng thứ i chứa hai số nguyên dương W_i, V_i cách nhau ít nhất một dấu cách

Output: file văn bản BAG.OUT

• Dòng 1: Ghi giá trị lớn nhất tên trộm có thể lấy
• Dòng 2: Ghi chỉ số những gói bị lấy

BAG.INP		BAG.OUT
5	11	11
3	3	5 2 1
4	4
5	4
9	10
4	4

Cách giải:

Nếu gọi F[i, j] là giá trị lớn nhất có thể có bằng cách chọn trong các gói {1, 2, …, i} với giới hạn trọng lượng j, thì giá trị lớn nhất khi được chọn trong số n gói với giới hạn trọng lượng M chính là F[n, M].

3.2.1. Công thức truy hồi tính F[i, j].

Với giới hạn trọng lượng j, việc chọn tối ưu trong số các gói {1, 2, …,i - 1, i} để có giá trị lớn nhất sẽ có hai khả năng:

• Nếu không chọn gói thứ i thì F[i, j] là giá trị lớn nhất có thể bằng cách chọn trong số các gói {1, 2, …, i - 1} với giới hạn trọng lượng là j, tức là F[i, j] = F[i - 1, j]
• Nếu có chọn gói thứ i (tất nhiên chỉ xét tới trường hợp này khi mà W_i <= j) thì F[i, j] bằng giá trị gói thứ i là V_i cộng với giá trị lớn nhất có thể có được bằng cách chọn trong số các gói {1, 2, …, i - 1} với giới hạn trọng lượng j - W_i. Tức là về mặt giá trị thu được: F[i, j] = V_i + F[i - 1, j - W_i]

Vì theo cách xây dựng F[i, j] là giá trị lớn nhất có thể, nên F[i, j] sẽ là max trong 2 giá trị thu được ở trên.

3.2.2. Cơ sở quy hoạch động:

Dễ thấy F[0, j] = giá trị lớn nhất có thể bằng cách chọn trong số 0 gói = 0.

3.2.3. Tính bảng phương án:

Bảng phương án F gồm n + 1 dòng, M + 1 cột, trước tiên được điền cơ sở quy hoạch động: Dòng 0 gồm toàn số 0. Sử dụng công thức truy hồi, dùng dòng 0 tính dòng 1, dùng dòng 1 tính dòng 2, v.v… đến khi tính hết dòng n.

3.2.4. Truy vết:

Tính xong bảng phương án thì ta quan tâm đến F[n, M] đó chính là giá trị lớn nhất thu được khi chọn trong cả n gói với giới hạn trọng lượng M. Nếu F[n, M] = F[n - 1, M] thì tức là không chọn gói thứ n, ta truy tiếp F[n - 1, M]. Còn nếu F[n, M] ¹ F[n - 1, M] thì ta thông báo rằng phép chọn tối ưu có chọn gói thứ n và truy tiếp F[n - 1, M - W_n]. Cứ tiếp tục cho tới khi truy lên tới hàng 0 của bảng phương án.

P_3_03_3.PAS * Bài toán cái túi

program The_Bag;

const
  InputFile = 'BAG.INP';
  OutputFile = 'BAG.OUT';
  max = 100;

var
  W, V: Array[1..max] of Integer;
  F: array[0..max, 0..max] of Integer; n, M: Integer;

procedure Enter;
  var
    i: Integer; fi: Text;
  
  begin
    Assign(fi, InputFile); Reset(fi); ReadLn(fi, n, M);
    for i := 1 to n do
      ReadLn(fi, W[i], V[i]);
    Close(fi);
  end;

procedure Optimize; {Tính bảng phương án bằng công thức truy hồi}
  var
    i, j: Integer;   
  begin
    FillChar(F[0], SizeOf(F[0]), 0); {Điền cơ sở quy hoạch động}
    for i := 1 to n do for j := 0 to M do
      begin {Tính F[i, j]}
        F[i, j] := F[i - 1, j]; {Giả sử không chọn gói thứ i thì F[i, j] = F[i - 1, j]}
        {Sau đó đánh giá: nếu chọn gói thứ i sẽ được lợi hơn thì đặt lại F[i, j]}
        if (j >= W[i]) 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 Trace; {Truy vết tìm nghiệm tối ưu}
  var
    fo: Text;

  begin
    Assign(fo, OutputFile);
    Rewrite(fo);
    WriteLn(fo, F[n, M]); {In ra giá trị lớn nhất có thể kiếm được}
    while n <> 0 do {Truy vết trên bảng phương án từ hàng n lên hàng 0}
    begin
      if F[n, M] <> F[n - 1, M] then {Nếu có chọn gói thứ n}
        begin
          Write(fo, n, ' ');
          M := M - W[n]; {Đã chọn gói thứ n rồi thì chỉ có thể mang thêm được trọng lượng M - Wn nữa thôi}
        end;
      Dec(n);
    end;
    Close(fo);
  end;

begin
  Enter;
  Optimize;
  Trace;
end.