Bài toán cái ba lô (Knapsack problem) là một bài toán tối ưu hóa cổ điển trong lý thuyết thuật toán và khoa học máy tính. Bài toán này có nhiều biến thể, nhưng biến thể phổ biến nhất là bài toán ba lô 0/1 (0/1 Knapsack problem).

Trong bài toán ba lô 0/1, bạn có một ba lô có sức chứa cố định và một tập hợp các vật phẩm, mỗi vật phẩm có một trọng lượng và giá trị nhất định. Mục tiêu là chọn một tập hợp các vật phẩm để tối đa hóa tổng giá trị mà không vượt quá sức chứa của ba lô.

Dưới đây là mã C++ để giải quyết bài toán ba lô 0/1 bằng phương pháp quy hoạch động:

```cpp
#include
#include
#include

using namespace std;

// Hàm giải quyết bài toán ba lô 0/1 bằng quy hoạch động
int knapsack(int W, vector& weights, vector& values, int n) {
// Tạo bảng DP để lưu trữ giá trị tối ưu
vector> dp(n + 1, vector(W + 1, 0));

// Duyệt qua tất cả các vật phẩm
for (int i = 1; i <= n; ++i) {
for (int w = 0; w <= W; ++w) {
if (weights[i - 1] <= w) {
dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
} else {
dp[i][w] = dp[i - 1][w];
}
}
}

// Giá trị tối ưu sẽ nằm ở dp[n][W]
return dp[n][W];
}

int main() {
int n; // Số lượng vật phẩm
int W; // Sức chứa của ba lô

cout << "Nhập số lượng vật phẩm: ";
cin >> n;

cout << "Nhập sức chứa của ba lô: ";
cin >> W;

vector weights(n);
vector values(n);

cout << "Nhập trọng lượng và giá trị của từng vật phẩm:\n";
for (int i = 0; i < n; ++i) {
cout << "Vật phẩm " << i + 1 << ":\n";
cout << "Trọng lượng: ";
cin >> weights[i];
cout << "Giá trị: ";
cin >> values[i];
}

int max_value = knapsack(W, weights, values, n);
cout << "Giá trị tối đa có thể đạt được là: " << max_value << endl;

return 0;
}
```

### Giải thích mã nguồn:
1. **Khởi tạo bảng DP**: `dp[i][w]` lưu trữ giá trị tối đa có thể đạt được với `i` vật phẩm đầu tiên và sức chứa `w`.
2. **Duyệt qua các vật phẩm**: Sử dụng hai vòng lặp để duyệt qua tất cả các vật phẩm và các mức trọng lượng từ 0 đến W.
3. **Cập nhật bảng DP**: Nếu trọng lượng của vật phẩm hiện tại nhỏ hơn hoặc bằng `w`, chúng ta có hai lựa chọn:
- Không chọn vật phẩm hiện tại: `dp[i][w] = dp[i - 1][w]`
- Chọn vật phẩm hiện tại: `dp[i][w] = dp[i - 1][w - weights[i - 1]] + values[i - 1]`
- Chọn giá trị lớn hơn giữa hai lựa chọn trên.
4. **Kết quả**: Giá trị tối ưu sẽ nằm ở `dp[n][W]`.

Bạn có thể chạy chương trình này và nhập vào số lượng vật phẩm, sức chứa của ba lô, trọng lượng và giá trị của từng vật phẩm để tìm giá trị tối đa có thể đạt được.