Bài toán ba lô có số lượng đồ vật không hạn chế

BÀI TOÁN

Cho n vật có khối lượng lần lượt là a1, a2, …, an và giá trị lần lượt là v1, v2, …, vn, mỗi vật có số lượng không hạn chế.

Cho một ba lô có tải trọng là m

Yêu cầu chọn một số vật để vào ba lô sao cho tổng khối lượng của các vật không vượt quá m và tổng giá trị của các vật là lớn nhất có thể.

Dữ liệu vào:

- Dòng đầu ghi số n và m

- Dòng thứ i trong n dòng tiếp theo, mỗi dòng ghi 2 số ai và vi

Kết quả: 

Ghi tổng giá trị lớn nhất tìm được.

Ví dụ:

Input

6 10

2 1

4 10

7 10

4 7

1 2

9 12

Output

24

 

HƯỚNG DẪN

Gọi f[i, j] là tổng giá trị lớn nhất khi chọn i vật đầu tiên sao cho tổng khối lượng không vượt quá j. Khi đó ta có:

• Cơ sở Quy hoạch động f[0, j] = 0 (j = 0...m)
• Kết quả cần tìm: f[n, m]
• f[i, j] được tính như sau: Gọi k là số lượng vật thứ i được chọn, khi đó ta có:

                        f[i, j] = max(f[i - 1, j - k*ai] + k*vi / 0 ≤ k ≤ [j / ai]) 

                       trong đó [j / ai] là phần nguyên khi chia j cho ai

Đoạn code cho công thức trên như sau:

for (int j = 0; j <= m; ++j) f[0][j] = 0;

for (int i = 1; i <= n; ++i) {

  for (int j  = 1; j <= m; ++j) {

    f[i][j] = f[i-1][j];

    for (int k = 1; k <= j/a[i]; ++k) {

      f[i][j] = max(f[i][j], f[i-1][j-k*a[i]] + k*v[i]);

    }

  }

}

BÀI TẬP

1. Viết thêm đoạn code truy vết cho bài toán trên (cho biết thứ tự và số lượng các vật được chọn).
2. Tối ưu bộ nhớ (chuyển về sử dụng 2 mảng 1 chiều thay cho mảng 2 chiều f) .
3. Giải bài toán cái ba lô với điều kiện hạn chế về số lượng các vật (vật thứ i có số lượng là ci)