LeetCode 补充题 102. 0-1 背包的最大价值
题目描述
牛客原题： ✅ 补充题 102. 0-1 背包的最大价值
给你一个容量为
capacity的背包，以及长度相同的两个数组volumes和values。第i件物品的体积为volumes[i]，价值为values[i]。每件物品至多选择一次。请返回所选物品总体积不超过
capacity时，可以获得的最大总价值。背包不需要恰好装满。
示例 1：
输入：
capacity = 5, volumes = [2,3,4], values = [3,4,5]
输出：7
解释： 选择前两件，体积为 2+3=5，价值为 3+4=7，每件只使用一次。
提示：
- 容量及物品数均不超过
1000。 - 物品体积为正数、价值为非负数且不超过
1000。 - 每件至多取一次。
- 不要求恰好装满。
题意分析
每件物品只有取或不取两种选择，且最多使用一次。容量只是上限，不要求装满，因此什么都不选也是价值为 0 的合法方案。
枚举所有子集会产生指数级分支；处理完相同前缀物品、拥有相同容量上限的情况，只需要保留价值最大的结果。由此按物品推进，用容量作为动态规划状态。
解法：容量倒序的 01 背包
核心思路
[!blue]
dp[c]表示只使用已经处理的物品、总体积不超过c时的最大价值。初始全为 0，表示尚未选物品。对体积为
v、价值为w的当前物品，不取它就保留旧的dp[c]；取它则需要给此前物品留下c - v的容量，候选价值为dp[c - v] + w。仅当c >= v时比较这两个选择。容量必须从大到小更新：读取较小的
dp[c - v]时，它尚未使用当前物品，才能保证每件至多取一次。若正序更新，读取的状态可能已经包含当前物品，便会重复选取。处理全部物品后，dp[capacity]就是容量上限下的最优值。
解题步骤
- 建立容量上限为 c 时的最大价值数组，初始为 0，表示可不选任何物品。
- 逐个物品从大容量向小容量更新，比较不选与选择当前物品。
- 返回完整容量的最优值，不要求恰好装满。
代码实现
class Solution {
public int knapsack(int capacity, int[] volumes, int[] values) {
int[] dp = new int[capacity + 1];
for (int i = 0; i < volumes.length; i++) {
for (int c = capacity; c >= volumes[i]; c--) {
dp[c] = Math.max(dp[c], dp[c - volumes[i]] + values[i]);
}
}
return dp[capacity];
}
}
func knapsack(capacity int, volumes, values []int) int {
dp := make([]int, capacity+1)
for i, v := range volumes {
for c := capacity; c >= v; c-- {
dp[c] = max(dp[c], dp[c-v]+values[i])
}
}
return dp[capacity]
}
复杂度分析
- 时间复杂度：$O(nC)$，
n为物品数，C为背包容量；每件最多枚举C个容量。- 空间复杂度：$O(C)$，只保存一维容量状态。
关键点总结
[!green]
倒序让前驱仍属于上一批物品；初始化为 0 对应不要求恰好装满，恰好装满则要另设不可达状态。
易错点总结
[!yellow]
容量顺序改成递增会变成完全背包；本题不要求恰好装满。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 416. 分割等和子集 | 中等 | 同样每个物品最多一次，原题状态是半和是否可达，本题状态是容量内最大价值。 |
| 474. 一和零 | 中等 | 从一维容量扩展到两种资源限制，两个容量维度也需要倒序以避免重复使用。 |