#include <iostream>
// #include <bits/stdc++.h>  // memset
 
#define max(a, b) ((a)>(b)?(a):(b))
 
class Knapsack {
public:
    /**
     * 01背包問(wèn)題(每個(gè)物品只能有1個(gè)或者不選, 不能有多個(gè)) 動(dòng)態(tài)規(guī)劃
     * @param n 候選物品數(shù)量
     * @param w int[] n個(gè)物品的重量(weight)
     * @param v int[] n個(gè)物品占價(jià)值(value)
     * @param cap int 背包最大重量,限制w參數(shù)
     * @param x int[] 選取哪些物品 0不選/1選取
     * @return int 背包最大價(jià)值
     */
    static int solution(int n, const int w[], const int v[], int cap, int x[]) {
        int i, j;
        int dp[n+1][cap+1]; // 存放迭代結(jié)果
        // memset(dp, 0, sizeof(dp));
        // 初始化第0列
        for (i=0; i <= n; i++) {
            dp[i][0] = 0;
        }
        // 初始化第0行
        for (j=1; j <= cap; j++) {
            if (w[0] <= j) {
                dp[0][j] = v[0];
            } else {
                dp[0][j] = 0;
            }
        }
 
        // 計(jì)算第i行，進(jìn)行第i次迭代
        for (i = 1; i <= n; i++) {
            for (j = 1; j <= cap; j++) {
                if (j < w[i]) {
                    dp[i][j] = dp[i-1][j];
                } else {
                    dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);
                }
            }
        }
        // 求裝入背包的物品
        for (i = n, j = cap; i >= 0; i--) {
            if (dp[i-1][j] != dp[i][j]) {
                x[i] = 1;
                j -= w[i];
            } else {
                x[i] = 0;
            }
        }
        return dp[n][cap];
    }
};
 
int main() {
    int w[] = {2,2,6,5,4};  // 每個(gè)物品的重量
    int v[] = {6,3,5,4,6};  // 每個(gè)物品的價(jià)值
    int cap = 10;    // 背包總重量
/*
    int w[] = { 1, 3, 4};
    int v[] = {15,20,30};
    int cap = 4;
    */
 
    int sz = sizeof(w)/sizeof(w[0]);
    int x[] = {0,0,0,0,0};   // 每個(gè)物品要(1)不要(0)放入背包
    int ans = Knapsack::solution(sz, w, v, cap, x);
    std::cout << "max value=" << ans << std::endl;
    std::cout << "[" << x[0];
    for (int i = 1; i <sz; i++) {
        std::cout <<", "<< x[i];
    }
    std::cout <<"]\n";
 
    return 0;
}

image.png