描述

有n个物品和一个容积为V的背包，每个物品i都有体积cost[i]和价值valum[i]，问如何选取物品使得放入背包的物品价值之和最大。

思路

01背包的特点就是每种物品都只有一个，所以每个物品只有拿和不拿两种状态。

我们用dp[i][j]来储存将前i件物品放入体积为j的背包中物品价值之和最大值，那么状态转移方程便是在放得下的情况下 $dp[i][j]=Max \begin{cases} dp[i-1][j] &\mbox{不拿第i个，状态跟i-1一样}\\ dp[i-1][j-cost[i]]+valum[i] &\mbox{拿第i个，那么就把前cost[i]体积的物品拿走再放} \end{cases}$

$(j:0 \to V,i:0 \to n)$

这样最后求出来的dp[n][V]就是最后答案。

优化

上面的时间复杂度是O(NV)已经无法再优化了,而空间复杂度可以优化到O(N)：我们用二维数组无非是为了保证状态转移方程里的dp[i-1][j-cost[i]]是上一个物品推出来的，如果我们直接改成dp[j]=max(dp[j],dp[j-cost[i]]+valum[i])的话，在$(j:0 \to V)$过程进行到后面的时候,dp[j-cost]有可能是已经在前面就放了i物品的状态，此时再+valumi就不符合每种物品都只有一个的题意了。

实际上。如果我们在遍历j的时候，采用逆序，即$(j:V \to 0)$，就可以保证dp[j-cost[i]]始终是i-1物品推出的。
核心代码如下
1
2
3
for(int i=1;i<=n;i++)
     for(int j=V;j>=cost[i];j--)
        dp[j]=max(dp[j],dp[j-cost[i]]+valum[i]);

初始化

如果题目没有要求必须装满，那么我们只要将dp数组全部置为0即可。

如果必须装满，我们就将dp[0]初始化为0，其他初始化为$-\infty$，$(j:V \to 0)$时每次判断dp[j-cost]是否>=0，是的话就进行状态转移。(自行体会，逃.jpg)

例题

板子题：洛谷1048

变式：洛谷1164

变式：2018年全国多校算法寒假训练营练习比赛(第二场) problem B（需要一个微妙的预处理）