背包难题：价值最大化
面对一堆物品，每个都拥有独特的重量和价值，如何将它们塞进有限负重的背包，使其总价值最大化？这就是经典的“背包难题”。动态规划提供了一种巧妙的解决方案。
核心步骤
-
构建价值矩阵：创建一个二维数组（dp），其中dp[i][j]代表考虑前i个物品，在背包容量为j的限制下，所能获得的最大价值。初始状态下，dp[0][j]皆为0，因为没有任何物品可选。
-
逐个分析：对于每个物品i和可能的重量j，我们有两种选择：放入或不放入背包。
- 放入：若物品i的重量不超过j，则dp[i][j]为dp[i-1][j-weight[i]] + value[i]，即前i-1个物品在剩余容量下的最大价值加上物品i的价值。
- 不放入：dp[i][j]则为dp[i-1][j]，即前i-1个物品在当前容量下的最大价值。 最终，dp[i][j]取两者中的较大值。
-
获取答案：dp数组的最后一项dp[n][W]（n为物品总数，W为背包容量）即为最终结果，代表在给定限制下，背包可容纳的最大价值。
举例说明
假设我们有3个物品，其重量和价值分别为：
| 物品 | 重量 | 价值 |
|---|---|---|
| 物品1 | 2 | 6 |
| 物品2 | 3 | 10 |
| 物品3 | 5 | 12 |
背包最大承重为5。通过动态规划，我们可以得出dp[3][5] = 16，即选择物品1和物品3，总价值最大。