一类经典的背包问题

0/1背包

有N件物品和一个容量为V的背包。第i件物品的体积是c[i], 价值是w[i], 求解将哪些物品放入背包中使价值最大。
一个错误的思路就是贪心，然而是错误的。

思路

适用的范围：仅限制于整数，当然浮点数的范围很小的时候，那么可以转变成整数。

• 状态设计：dp[i][j]: 表示前面的i件物品，放入到容量为j的背包所能获得的最大的价值
• 状态转移方程: f[i][j] = max{f[i-1][j], f[i-1][j-c[i]]+w[i]}
• 边界：
• 结果:dp[N][1~V]

时间复杂度无法优化，空间复杂度依旧可以优化：
f[i]仅与f[i-1]有关,注意枚举体积的时候必须逆序枚举。否则会变成完全背包问题。

1
2
3
4
5

for(int i=0; i<N; i++){
        for(int j = V; j>=c[i]; j--){
            dp[j] = max(dp[j], dp[j-c[i]]+w[i]);
        }
    }

初始化：
若要求背包放满：

f[0] = 0, f[1~N] = \(-\infty\), 那么解就是f[N]

若不要求背包放满：

f[0~N] = 0;

完全背包

物品无限

1
2
3
4
5

for(int i=0; i<N; i++){
        for(int j = c[i]; j<=V; j++){
            dp[j] = max(dp[j], dp[j-c[i]]+w[i]);
        }
    }

多重背包

N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件的费用是c[i],价值w[i],求解不超过件数的限制，使价值最大。
0/1背包和完全背包是多重背包的特例。

二进制拆分：
1， 2， 4，… \(2^k, n[i]-2_{k+1}+1\).这些数的和为n[i], 且任意数的组合可以得到0~n[i]之间的数字。

代码

1
2
3
4
5
6
7
8

for(int i=0; i<N; i++){
    for(int k=1; k<n[i]; n[i]-=k, k<<=1)
        for(int j=V; j>=k*c[i]; j--)
            dp[j] = max(dp[j], dp[j-k*c[i]]+k*w[i]);
    for(int j=V; j>=n[i]*c[i]; j--){
        dp[j] = max(dp[j], dp[j-n[i]*c[i])+n[i]*w[i];
    }
}

优化

单调队列怎么优化？

二维背包

第i件物品有两种代价a[i], b[i].

• 状态描述：dp[i][j][k],前i件物品，第一种代价花费j, 第二种代价花费k的最大价值
• 状态转移方程：dp[i][j][k] = max{dp[i-1][j][k], dp[i-1][v-a[i]][u-b[i]]+w[i]}

当然和前面的一样，可以减小空间复杂度。

分组背包

把所有的物品分成若干个组，每个组中最多选择一件，求最大价值。

• 状态描述：dp[k][v]:表示前k组物品花费费用v能够取到的最大的价值。
• 状态转移方程：dp[k][j] = max{dp[k-1][j], dp[k-1][j-c[i]]+w[i]}

代码

注意枚举的顺序！！
因为这一组中要么都不选，要么只能选择一个。所以要倒过来枚举(01背包就是倒过来枚举的，这样最多只能一个)。

1
2
3
4
5
6
7
8
9
10

vector<vector<int> > G;
    for(int k=0; k<G.size(); k++){
        for(int j=V; j; j--){
            for(int i=0; i<G[k].size(); i++){
                int p = G[k][i];//物品的编号
                if(c[p]>j) continue;
                dp[j] = max(dp[j], dp[j-c[p]]+w[p]);
            }
        }
    }

未解决的问题