Trong siêu thị có n đồ vật (n ≤ 1000), với mỗi đồ vật thứ i có trọng lượng là W[i] ≤ 1000 và giá trị V[i] ≤ 1000. 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 ≤ 1000). Hãy xác định tập hợp đồ vật tối ưu để tên trộm lấy, sao cho tổng giá trị của những đồ vật này là lớn nhất.

Giải quyết bài toán trong hai trường hợp sau:

• Mỗi đồ vật chỉ được chọn một lần.
• Mỗi đồ vật có thể được chọn nhiều lần (không hạn chế số lần).

Input Data:

File văn bản Bag.inp

Dòng 1: Hai số nguyên n và M, cách nhau ít nhất một dấu cách.

n dòng tiếp theo: Mỗi dòng chứa hai số nguyên Wi và Vi, lần lượt là trọng lượng và giá trị của đồ vật thứ i.

Output Data:

File văn bản bag.out

Ghi giá trị lớn nhất mà tên trộm có thể lấy được từ tập hợp các đồ vật được chọn.

2. Ý tưởng bài toán

2.1. Xây dựng Bảng DP (Programing Dynamic)

• Sử dụng một ma trận DP có kích thước (n+1) x (M+1), trong đó n là số lượng đối tượng, và M là trọng lượng tối đa của túi.
• DP[i][j] sẽ đại diện cho giá trị lớn nhất có thể đạt được với i đối tượng và túi có trọng lượng tối đa là j.

Giả sử có 4 đối tượng (n = 4) và trọng lượng tối đa của túi là 7 (M = 7). Các trọng lượng và giá trị của các đối tượng được đưa vào ma trận như sau:

Ở đây:

• Hàng thứ i của bảng (i từ 0 đến 4) đại diện cho việc xem xét i đối tượng.
• Cột thứ j của bảng (j từ 0 đến 7) đại diện cho việc xem xét túi có trọng lượng tối đa là j.

Các giá trị trong bảng phản ánh giá trị lớn nhất có thể đạt được với số lượng đối tượng và trọng lượng túi tương ứng. Ví dụ, giá trị lớn nhất mà tên trộm có thể lấy được là 9, và để đạt được giá trị này, có thể chọn đối tượng 1, 2 và 4 (có tổng trọng lượng là 3 + 2 + 1 = 6).

2.2. Viết công thức cập nhật DP:

• Dùng công thức sau để cập nhật giá trị của DPi][j]:

DP[i][j] = max(DP[i-1][j], DP[i-1][j - W[i]] + V[i])

Trong đó, W[i] là trọng lượng của đối tượng thứ i, và V[i] là giá trị của đối tượng thứ i.

2.3. Truy vết để xác định đối tượng được chọn:

• Bắt đầu từ DP[n][M] (góc phải dưới của ma trận), ta có thể theo dõi ngược lên để xác định các đối tượng được chọn.

for i from 1 to n:

for j from 1 to M:

if W[i] > j:

DP[i][j] = DP[i-1][j]

else:

DP[i][j] = max(DP[i-1][j], DP[i-1][j - W[i]] + V[i])

• Giá trị lớn nhất có thể đạt được sẽ nằm ở DP[n][M]. Ngoài ra, để xác định các đối tượng được chọn, ta có thể sử dụng truy vết từ DP[n][M] ngược lên.
• Lưu ý rằng đối với bài toán Cái Túi 0/1, mỗi đối tượng chỉ được chọn một lần. Đối với phiên bản không giới hạn số lần chọn (Bài toán Cái Túi Vô Hạn), cách tiếp cận có thể khác nhau.

3. Code bài toán cái túi C++

Dưới đây là code mẫu bài toán cái túi C++:

include

include

using namespace std;

const long long mod = 1e9 + 7;

void enter(int &n, int &K, vector &a) {

cin >> n >> K;

a.resize(n + 1);

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

cin >> a[i];

}

void solution(int n, int K, const vector &a) {

vector> dp(n + 1, vector(K + 1, 0));

for (int i = 0; i <= n; ++i)

dp[i][0] = 1;

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

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

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

if (j >= a[i]) {

dp[i][j] = (dp[i][j] + dp[i - 1][j - a[i]]) % mod;

}

}

}

cout << dp[n][K];

}

int main() {

int n, K;

vector a;

enter(n, K, a);

solution(n, K, a);

return 0;

}

Trên đây ICANTECH đã cùng bạn tìm hiểu về bài toán cái túi thông qua ý tưởng và code bài toán. Hi vọng bài viết đã giúp bạn có thêm những kiến thức về bài toán, thuật toán giải bằng C++.