背包问题

01 背包

有 $N$ 件物品和一个容量为 $V$ 的背包。放入第 $i$ 件物品耗费的费用是 $C_i$，得到的价值是 $W_i$。求解将哪些物品装入背包可使价值总和最大。即限定每个物品要么拿（1个）要么不拿（0个）。

用$f[n, C]$表示将$n$个物品放入容量为$C$的背包获得的最大收益，而第$i$个物品无非是拿与不拿， \(f[i,C] = max(f[i - 1, C], f[i - 1, C - W[i] + V[i])\)

第一种时间复杂度为$O(nC)$

int zero_one_knapsack(vector<int>& v, vector<int>& w, int n , int C){
    //每个物品有w和v两种属性,总共有n个物品
    //整个背包只能携带一定的物品 sum(w_i) <= C 求max(sum(v_i))
    vector<vector<int>> dp(n, vector<int>(C + 1));
    for(int i = 0 ; i < n ; i ++) dp[i][0] = 0;
    for(int j = 1; j <= C ; j ++) {
        if(j >= w[0]){
            dp[0][j] = v[0];
        }else
            dp[0][j] = 0;
    }

    for(int i = 1; i < n ; i ++){
        for(int j = 1; j <= C ; 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]);
            }
        }
    }
    return dp[n  - 1][C];
}

空间压缩后

int zero_one_knapsack_opt(vector<int>& v, vector<int>& w, int n , int C) {
    vector<int> f(C + 1);
    for(int i = 0 ; i < n ; i++){
        for(int j = C ; j >= w[i] ; j --){
            f[j] = max(f[j], f[j  - w[i]] + v[i]);
        }
    }

    return f[C];
}

完全（无界）背包问题

如果不限定每种物品的数量，同一样物品想拿多少拿多少，则问题称为无界或完全背包问题。

\(f[i][j] = max(f[i - 1][j], f[i - 1][ j - k*w[i] ] + k * v[i])\) 这里，$0 <= kw[i] <= j$,此时复杂读就变为$O(nC * \sum (C / w[i]))$

多重（有界）背包问题

如果限定物品i最多只能拿$m[i]$个，则问题称为有界或多重背包问题。

\[f[i][j] = max{f[i - 1][j - k * w[i]] + k * v[i] | 0 <= k <= m[i]}\]