选取货物 - 题解（0-1背包问题）
题目描述
若干货物的信息记录于二维数组 goods 中，其中 goods[i] = [weight,value]，表示第 i 个货物的价值为 value，重量为 weight。从中选取一些货物，求当选取的货物总重量不超过 maxWeight 时的货物最大价值总和。
示例：
输入：
goods = [[7,7],[5,1],[8,9],[5,7],[6,8]], maxWeight = 21输出: 24解释：
选取第 2、3、4个货物（下标从 0 开始），此时商品重量总和为 8 + 5 + 6 = 19，商品价值总和为 9 + 7 + 8 = 24。提示：
- 1 <= goods.length <= 100
- 1 <= goods[i][0] <= 10^5
- 1 <= goods[i][1] <= 100
- 1 <= maxWeight <= 10^7
问题分析
这是一个典型的0-1背包问题，每个货物只能选择拿或不拿，不能部分选取。
问题特征：
- 物品有限：总共有 n 个货物
- 容量限制：背包最大承重为 maxWeight
- 每个物品有两个属性：重量和价值
- 目标：在不超过背包容量的前提下，最大化物品的总价值
决策过程：
对于每个货物，我们面临两个选择：
- 选择该货物：获得其价值，但消耗背包容量
- 不选择该货物：不获得价值，也不消耗容量
解题思路
动态规划方法
状态定义：
- dp[i][w] 表示考虑前 i 个货物，背包容量为 w 时能获得的最大价值
状态转移方程：
dp[i][w] = max(dp[i-1][w], // 不选择第i个货物dp[i-1][w-weight[i]] + value[i] // 选择第i个货物（如果容量足够）
)边界条件：
- dp[0][w] = 0（没有货物时，价值为0）
- dp[i][0] = 0（背包容量为0时，价值为0）
算法过程
以示例 goods = [[7,7],[5,1],[8,9],[5,7],[6,8]], maxWeight = 21 为例：
动态规划表格构建过程
货物信息：
索引 重量 价值
0 7 7
1 5 1
2 8 9
3 5 7
4 6 8构建dp表格（部分关键状态）：
| i\w | 0 | 5 | 6 | 7 | 8 | 10 | 11 | 12 | 13 | 18 | 19 | 21 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 7 | 7 | 7 | 7 | 7 | 7 | 7 | 7 | 7 |
| 2 | 0 | 1 | 1 | 7 | 7 | 8 | 8 | 8 | 8 | 8 | 8 | 8 |
| 3 | 0 | 1 | 1 | 7 | 9 | 9 | 9 | 9 | 16 | 16 | 16 | 17 |
| 4 | 0 | 7 | 7 | 8 | 9 | 14 | 16 | 16 | 16 | 16 | 23 | 24 |
| 5 | 0 | 7 | 8 | 8 | 9 | 14 | 16 | 17 | 17 | 22 | 23 | 24 |
最终答案： dp[5][21] = 24
最优解构成
选择的货物：
- 货物2：重量8，价值9
- 货物3：重量5，价值7
- 货物4：重量6，价值8
- 总重量：8 + 5 + 6 = 19 ≤ 21 ✓
- 总价值：9 + 7 + 8 = 24
算法实现
动态规划
Java版本
/*** 2. 选取货物* 动态规划*/
class Solution {public int maximumGoodsValue(int[][] goods, int maxWeight) {int n = goods.length;// dp[i][w] 表示考虑前i个货物，背包容量为w时的最大价值int[][] dp = new int[n + 1][maxWeight+1];for (int i = 1; i <= n; i++) {int weight = goods[i-1][0]; // 当前货物重量int value = goods[i-1][1]; // 当前货物价值// 遍历每个可能的背包容量for (int w = 0; w <= maxWeight; w++) {// 不选择当前货物dp[i][w] = dp[i-1][w];// 如果背包容量足够，考虑选择当前货物if (w >= weight) {dp[i][w] = Math.max(dp[i][w], dp[i-1][w-weight] + value);}}}return dp[n][maxWeight];}
}C# 版本
/*** 2. 选取货物* 动态规划*/
public class Solution
{public int MaximumGoodsValue(int[][] goods, int maxWeight){int n = goods.Length;int[,] dp = new int[n + 1, maxWeight + 1];for (int i = 1; i <= n; i++){int weight = goods[i - 1][0];int value = goods[i - 1][1];for (int w = 0; w <= maxWeight; w++){dp[i, w] = dp[i - 1, w];if (w >= weight){dp[i, w] = Math.Max(dp[i, w], dp[i - 1, w - weight] + value);}}}return dp[n, maxWeight];}
}空间优化
Java版本
/*** 2. 选取货物* 动态规划，空间优化*/
class Solution {public int maximumGoodsValue(int[][] goods, int maxWeight) {int n = goods.length;int[] dp = new int[maxWeight + 1];for (int i = 1; i <= n; i++) {int weight = goods[i - 1][0];int value = goods[i - 1][1];// 从后往前遍历，避免重复计算for (int w = maxWeight; w >= weight; w--) {dp[w] = Math.max(dp[w], dp[w - weight] + value);}}return dp[maxWeight];}
}C# 版本
/*** 2. 选取货物* 动态规划，空间优化*/
public class Solution
{public int MaximumGoodsValue(int[][] goods, int maxWeight){int n = goods.Length;int[] dp = new int [maxWeight + 1];for (int i = 1; i <= n; i++){int weight = goods[i - 1][0];int value = goods[i - 1][1];for (int w = maxWeight; w >= weight; w--){dp[w] = Math.Max(dp[w], dp[w - weight] + value);}}return dp[maxWeight];}
}复杂度分析
时间复杂度
- 二维DP版本：O(n × maxWeight)
- 需要填充 n × maxWeight 大小的表格
- 一维优化版本：O(n × maxWeight)
- 虽然空间优化了，但时间复杂度不变
空间复杂度
- 二维DP版本：O(n × maxWeight)
- 一维优化版本：O(maxWeight)
进一步优化思路：状态转换
核心洞察
观察到物品价值范围很小（最大100），而背包容量很大（最大10^7），我们可以转换DP的状态定义：
传统思路：
- 状态：dp[w] = 容量为w时的最大价值
- 转移：枚举容量，更新价值
优化思路：
- 状态：dp[v] = 达到价值v所需的最小重量
- 转移：枚举价值，更新重量
优化后的复杂度
- 最大总价值：100（物品数） × 100（单价值） = 10,000
- 时间复杂度：O(n × V) = O(100 × 10,000) = O(10^6) ，大幅优化
- 空间复杂度：O(V) = O(10,000) ，显著减少
算法详解
状态转移过程
让我们通过示例来理解算法过程：
输入： goods = [[7,7],[5,1],[8,9],[5,7],[6,8]], maxWeight = 21
初始化
maxTotalValue = 5 × 100 = 500
dp = [0, ∞, ∞, ∞, ..., ∞] // 长度为501处理物品0：[7,7]（重量7，价值7）
从 v=500 到 v=7：如果 dp[v-7] != ∞，则 dp[v] = min(dp[v], dp[v-7] + 7)v=7: dp[7] = min(∞, dp[0] + 7) = min(∞, 0 + 7) = 7结果：dp = [0, ∞, ∞, ∞, ∞, ∞, ∞, 7, ∞, ...]
含义：价值7需要重量7处理物品1：[5,1]（重量5，价值1）
v=8: dp[8] = min(∞, dp[7] + 5) = min(∞, 7 + 5) = 12
v=1: dp[1] = min(∞, dp[0] + 5) = min(∞, 0 + 5) = 5结果：dp = [0, 5, ∞, ∞, ∞, ∞, ∞, 7, 12, ∞, ...]
含义：价值1需要重量5，价值8需要重量12继续处理剩余物品...
最终找到在重量限制21内能达到的最大价值。
关键思想解释
- 状态定义转换：
- 传统：dp[重量] = 最大价值
- 优化：dp[价值] = 最小重量
- 为什么逆序遍历：
- 保证每个物品只被使用一次
- 避免在同一轮更新中重复使用同一物品
- 为什么这样优化有效：
- 价值范围小（最大10,000）
- 重量范围大（最大10^7）
- 通过转换状态，将复杂度从O(重量)降到O(价值)
算法实现
Java 版本
import java.util.Arrays;/*** 2. 选取货物* 按价值DP*/
class Solution {public int maximumGoodsValue(int[][] goods, int maxWeight) {int n = goods.length;// 计算最大可能的总价值int maxTotalValue = n * 100;// dp[v] 表示达到价值v所需的最小重量// 初始化为无穷大，表示无法达到该价值int[] dp = new int[maxTotalValue + 1];Arrays.fill(dp, Integer.MAX_VALUE);// 价值为0时，重量也为0dp[0] = 0;for (int i = 1; i <= n; i++) {int weight = goods[i - 1][0]; // 当前货物重量int value = goods[i - 1][1]; // 当前货物价值// 从高价值向低价值遍历，避免重复使用同一物品for (int v = maxTotalValue; v >= value; v--) {// 如果可以达到价值 v-value，则可以通过添加当前物品达到价值vif (dp[v - value] != Integer.MAX_VALUE) {dp[v] = Math.min(dp[v], dp[v - value] + weight);}}}// 找到最大价值，使其对应的重量不超过maxWeightint res = 0;for (int v = maxTotalValue; v >= 0; v--) {if (dp[v] <= maxWeight) {res = v;break;}}return res;}
}C# 版本
/*** 2. 选取货物* 按价值DP*/
public class Solution
{public int MaximumGoodsValue(int[][] goods, int maxWeight){int n = goods.Length;// 计算最大可能的总价值int maxTotalValue = 100 * n;// dp[v] 表示达到价值v所需的最小重量// 初始化为无穷大，表示无法达到该价值int[] dp = new int[maxTotalValue + 1];Array.Fill(dp, int.MaxValue);// 价值为0时，重量也为0dp[0] = 0;for (int i = 0; i < n; i++){int weight = goods[i][0];int value = goods[i][1];// 从高价值向低价值遍历，避免重复使用同一物品for (int v = maxTotalValue; v >= value; v--){// 如果可以达到价值 v-value，则可以通过添加当前物品达到价值vif (dp[v - value] != int.MaxValue){dp[v] = Math.Min(dp[v], dp[v - value] + weight);}}}// 找到最大价值，使其对应的重量不超过maxWeightint res = 0;for (int v = 0; v <= maxTotalValue; v++){if (dp[v] <= maxWeight){res = v;}}return res;}
}复杂度分析
- 时间复杂度：O(n × V) = O(100 × 10,000) = O(10^6)
- 空间复杂度：O(V) = O(10,000)
相比传统方法的O(10^9)时间复杂度，这是一个巨大的优化！