Các thuật ngữ như "Bài toán Cái Túi," hay "Bài toán Knapsack" đều là dạng bài toán tối ưu hóa trong tổ hợp. Để giải các bài toán này, chúng ta cần lựa chọn một số đối tượng để đặt vào một túi với trọng lượng giới hạn đã biết trước, sao cho tổng giá trị của các đối tượng đó là lớn nhất có thể. Trong bài viết dưới đây, hãy cùng ICANTECH tìm hiểu về bài toán cái túi với C++ nhé!
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:
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.
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:
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).
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.
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])
Dưới đây là code mẫu bài toán cái túi C++:
#include <iostream>
#include <vector>
using namespace std;
const long long mod = 1e9 + 7;
void enter(int &n, int &K, vector<int> &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<int> &a) {
vector<vector<long long>> dp(n + 1, vector<long long>(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<int> 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++.
Cảm ơn bạn đã đọc bài viết, nếu bạn đang quan tâm đến học lập trình thì hãy tham khảo ngay các khóa học lập trình dưới đây tại ICANTECH nhé
Nguồn ảnh: ICANTECH.