In các vật phẩm được chọn trong bài toán Cái ba lô 0/1 (0/1 Knapsack) trong C++

Bài toán Cái ba lô 0/1: Cho n vật, mỗi vật có trọng lượng wt[i] và giá trị val[i]. Ba lô chịu trọng lượng W. Chọn tập con vật sao cho tổng trọng lượng ≤ W và tổng giá trị lớn nhất. In ra trọng lượng các vật được chọn.

Thuật động (Dynamic Programming + Truy vết)

1. Xây bảng DP K[i][w] = giá trị lớn nhất dùng i vật đầu, trọng lượng ≤ w.
2. Công thức: K[i][w] = max(K[i-1][w], val[i-1] + K[i-1][w-wt[i-1]]) (nếu wt[i-1] ≤ w).
3. Truy vết từ K[n][W]: nếu K[i][w] != K[i-1][w] → vật i được chọn, trừ w và val, chuyển sang i-1.

Ví dụ minh họa (C++)

#include <bits/stdc++.h>
using namespace std;

void printknapSack(int W, int wt[], int val[], int n) {
    vector<vector<int>> K(n+1, vector<int>(W+1, 0));
    for (int i = 1; i <= n; ++i) {
        for (int w = 1; w <= W; ++w) {
            if (wt[i-1] <= w)
                K[i][w] = max(val[i-1] + K[i-1][w - wt[i-1]], K[i-1][w]);
            else
                K[i][w] = K[i-1][w];
        }
    }
    cout << "Gia tri lon nhat = " << K[n][W] << "\nTrong luong cac vat duoc chon:\n";
    int w = W;
    for (int i = n; i > 0 && K[n][W] > 0; --i) {
        if (K[i][w] != K[i-1][w]) {
            cout << wt[i-1] << " ";
            w -= wt[i-1];
        }
    }
    cout << endl;
}

int main() {
    int val[] = {50, 120, 70};
    int wt[] = {10, 20, 30};
    int W = 50;
    int n = sizeof(val)/sizeof(val[0]);
    printknapSack(W, wt, val, n);
    return 0;
}

Kết quả

Gia tri lon nhat = 190
Trong luong cac vat duoc chon:
30 20