01 knapsack

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

int main() {
    int N = 4;
    int backpack = 10; // 背包容量
    vector<int> weight = {0, 2, 3, 4, 5};
    vector<int> value = {0, 5, 6, 7, 8};
    vector<vector<int>> dp(N + 1, vector<int>(backpack + 1, 0));
    vector<vector<bool>> chosen(N + 1, vector<bool>(backpack + 1, false));

    for (int i = 1; i <= N; i++) {
        for (int j = 0; j <= backpack; j++) {
            if (weight[i] <= j) {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
                if (dp[i][j] > dp[i - 1][j]) {
                    // 如果dp[i][j]不是來自於上面dp[i-1][j]，就代表物品i有被選取
                    // 詳細參考https://www.geeksforgeeks.org/printing-items-01-knapsack/
                    chosen[i][j] = true; 
                }
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }

    cout << "max value: " << dp[N][backpack] << endl;

    // 通过 chosen 数组来找出所选择的物品
    int i = N, j = backpack;
    vector<int> selectedItems;
    while (i > 0 && j > 0) { // 物品序號>0 && 可用空間>0
        if (chosen[i][j]) { // 若有被選擇
            selectedItems.push_back(i); // 加入被選向量(selectedItems)中
            j -= weight[i]; // 可用空間扣掉該物品重量
        }
        i--; // 物品序號-1
    }

    cout << "selected: "; // 注意，要"逆"向輸出這樣東西才會保持原來的順序
    for (int i = selectedItems.size() - 1; i >= 0; i--) {
        cout << selectedItems[i] << " ";
    }
    cout << endl;

    return 0;
}

好資源

• 01背包，包含路徑回朔：https://www.geeksforgeeks.org/printing-items-01-knapsack/