01背包

Yama-lei2025年3月21日大约 2 分钟

01背包问题：

它的目标是：给定一组物品，每个物品有自己的重量和价值，在不超过背包容量的前提下，如何选择物品使得总价值最大。

将物品按照性价比进行排序，性价比高的优先选择，便利数组。

错误之处：可能出现背包留下很大的空隙，反而因为无法装满而没有达到总价值最大。

比如：有商品如下(value, space) (5,10) (1,1) (1,1) (1,1).如果背包大小为12的话，按照上面的算法，就会最终有9个空间的剩余。

Reference：咱就把0-1背包问题讲个通透！ - 知乎

使用动态规划，dp[i][j]表示，在index为0~i的物品里面随便选择，能获得的最大价值。

$$
dp[i][j]=max(dp[i-1][j],dp[i-1][j-space[i])]+value[i])
$$

代表的意思是：0~i的物品里面选最多j体积的物品，有两种可能：

取这两种可能的最大者

考虑到，如果体积j==0，那么一定有dp[i][j]==0;

如果i==0，那么有dp[i][j] = 0 if j<space[i] else j;

其他的情况，只要保证初始值不大于最终的正确值，通常来说可以初始化为0，除非有的物品价值为负数（此时应该赋值为一个很小的负数，理论上应该赋值$- \infin$）

比如说，如果某一个地方最终值应该是-19（在某些价值可能为负数的时候），在初始化的时候，不应该把这个地方赋值为0；

在遍历之前，我们先思考一下状态转移方程：
$$
dp[i][j]=max(dp[i-1][j],dp[i-1][j-space[i])]+value[i])
$$
发现我们的每一个新状态，都依赖于前面i,j值更小的状态；因此一定是要讲i，j从小往大的方向遍历。

可以参考一下这幅图：

图中那个点的值只依赖于ta上面的点和左上方的某个点，因此，只需要保证这个点左上方那一块全都正确地赋值，这个点就能得到正确的结果。