01背包问题之背包容量为什么要倒序遍历？(以C++代码具体实现为例)

首先是先阐述一下背包问题：

有n件物品和一个最多能背重量为w的背包。第i件物品的重量是weight[i],得到的价值是value[i]。每件物品只能用依次，求解将哪些物品装入背包里物品价值总和最大。

这里不解释代码的其他部分，只对代码中的背包容量遍历进行具体的解释，首先给出遍历部分的代码

for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
}

下面给出例子：

• 背包容量：bagWeight = 5
• 物品列表：
  • 物品 1：重量 weight[0] = 2，价值 value[0] = 3
  • 物品 2：重量 weight[1] = 3，价值 value[1] = 4

动态规划数组定义如下,也就是起始数组中元素初始化为0.

vector<int> dp(bagWeight+1,0)

 首先背包容量从小到大遍历(错误的方式)

1.遍历物品1

• j = 2：dp[2] = max(dp[2], dp[2 - 2] + 3) = max(0, 0 + 3) = 3
• j = 3：dp[3] = max(dp[3], dp[3 - 2] + 3) = max(0, 0 + 3) = 3
• j = 4：dp[4] = max(dp[4], dp[4 - 2] + 3) = max(0, 3 + 3) = 6
• j = 5：dp[5] = max(dp[5], dp[5 - 2] + 3) = max(0, 3 + 3) = 6

处理完物品 1 后，dp[] 数组变为 [0, 0, 3, 3, 6, 6]。可以看到k=4的时候，对dp[2]重复了计算，不符合01背包物品只能放一次的原则

2.遍历物品2

• j = 3：dp[3] = max(dp[3], dp[3 - 3] + 4) = max(3, 0 + 4) = 4 。
• j = 4：dp[4] = max(dp[4], dp[4 - 3] + 4) = max(6, 0 + 4) = 6，dp[4] 不变。
• j = 5：dp[5] = max(dp[5], dp[5 - 3] + 4) = max(6, 3 + 4) = 7。

处理完物品 2 后，dp[] 数组变为 [0, 0, 3, 4, 6, 7]。

然后是背包容量从大到小遍历(正确的方式)

1.遍历物品1

• j = 5：dp[5] = max(dp[5], dp[5 - 2] + 3) = max(0, 0 + 3) = 3
• j = 4：dp[4] = max(dp[4], dp[4 - 2] + 3) = max(0, 0 + 3) = 3
• j = 3：dp[3] = max(dp[3], dp[3 - 2] + 3) = max(0, 0 + 3) = 3
• j = 2：dp[2] = max(dp[2], dp[2 - 2] + 3) = max(0, 0 + 3) = 3

处理完物品 1 后，dp[] 数组变为 [0, 0, 3, 3, 3, 3]。可以看到这时候物品1没有被重复计算

2.遍历物品2

• j = 5：dp[5] = max(dp[5], dp[5 - 3] + 4) = max(3, 3 + 4) = 7
• j = 4：dp[4] = max(dp[4], dp[4 - 3] + 4) = max(3, 0 + 4) = 4
• j = 3：dp[3] = max(dp[3], dp[3 - 3] + 4) = max(3, 0 + 4) = 4

处理完物品 2 后，dp[] 数组变为 [0, 0, 3, 4, 4, 7]。

从上面可以看出，遍历顺序选择的时候，背包容量应该从大到小进行遍历，这样才符合01背包不重复拿取物品的原则。