完全背包

出自《背包九讲》

问题

有$N$种物品和一个容量为$V$的背包,每种物品都有无限个。放入第$i$种物品的的体积是$c_i$,价值是$w_i$。

求解最大价值是多少

思想

它和01背包类似,但又不完全相同。

因为当前的状态,比如$dp[i][j]$ 表示前$i$个物品,容量为$j$,的最大价值

它的转移可能是由$dp[i-1][j - k c[i]] + k w[i]$ 转移过来的, 如果去枚举$k$,那么复杂度必定爆炸。

如果我们用一维来表示$dp[j]$

那么更新$dp[j]$的时候,转移就为$dp[j] = Max(dp[j], dp[j-c[i]]+w[i])$

而此时$dp[j-c[i]]$是已经被更新过的。

代码

1
2
3
4
5
6
clr(dp, 0);
for (int i = 1; i <= N; i++) {
for (int j = c[i]; j <= V; j++) {
dp[j] = max(dp[j], dp[j - c[i]] + w[i]);
}
}
Thank you for your support!