Algorithms01

1

这里直接等效为：根据有限数组找到容量正好为11的背包，那么很容易就想到这里重量=价值。

不用再更改讲义了，请直接回答我：为什么重量=价值，判断条件是 dp[target] == target；而重量=1时，判断条件是dp[k] == sum/2？

好问题！这个区别的核心在于dp数组的含义完全不同：

🎯 情况1：重量=价值=nums[i]

dp[j] = 容量为j的背包，能装的最大价值

• 选择数字 [1, 5] 时：
  • 重量总和 = 1 + 5 = 6
  • 价值总和 = 1 + 5 = 6
  • 所以 dp[6] = 6

判断逻辑： dp[target] == target

• dp的下标target = 我们想要的数字之和
• dp的值target = 实际选中的数字之和
• 相等说明：我们真的选到了和为target的数字组合

🔄 情况2：重量=1，价值=nums[i]

dp[j] = 最多选择j个物品时，能获得的最大价值

• 选择数字 [1, 5] 时：
  • 重量总和 = 1 + 1 = 2（每个物品重量都是1）
  • 价值总和 = 1 + 5 = 6
  • 所以 dp[2] = 6

判断逻辑： 遍历所有k，找dp[k] == sum/2

• dp的下标k = 选中了多少个数字
• dp的值 = 选中数字的实际和
• 需要找：某种选择个数下，数字和正好是sum/2

💡 核心区别

建模方式	dp[j]的含义	下标j代表	值dp[j]代表	判断条件
重量=价值=nums[i]	容量j的最大价值	想要的数字和	实际数字和	dp[target]==target
重量=1,价值=nums[i]	选j个物品的最大价值	选择个数	实际数字和	dp[k]==sum/2

为什么第一种更好？

• 下标直接对应目标，判断一次就够
• 第二种需要遍历所有可能的选择个数，效率低

这就是为什么”分割等和子集”用重量=价值的建模——让dp的下标直接对应我们关心的目标值！