#P4421. 0/1背包问题
-
1000ms
Tried: 12
Accepted: 3
Difficulty: 6
0/1背包问题
解题思路
-
二维循环
- 定义
dp[i][j]:只用前i件物品、容量不超过j的最大价值。 - 转移:当
j ≥ v[i]时dp[i][j] = max(dp[i-1][j], dp[i-1][j - v[i]] + w[i]);否则dp[i][j] = dp[i-1][j]。 - 直观易懂,但空间
O(NV)。
- 定义
-
滚动数组优化
- 观察到第
i层只依赖第i-1层,压成一维dp[j]。 - 关键点:容量倒序(
j = V..v[i]),避免同一物品重复使用:dp[j] = max(dp[j], dp[j - v[i]] + w[i])。 - 时间
O(NV),空间降为O(V)。
- 观察到第
-
原地优化
- “可达剪枝”:维护“可达最大容量”
reachCap。处理第i件时,内层上界仅枚举到end = min(V, reachCap + v[i]),跳过永不可达区间,减少无效更新。 - “负无穷初始化”:令
dp[0]=0,其余dp[j]置为很小的负数(表示“不可达”)。转移前先判断dp[j - v]是否可达,代码更简洁安全。 - 忽略无效物品:
v[i] > V可直接跳过。 - 注意:此时
dp[j]表示“恰好容量为j的最大价值”,答案为max_{0≤j≤V} dp[j]。
- “可达剪枝”:维护“可达最大容量”
复杂度分析
- 时间复杂度:
O(N * V)。 - 空间复杂度:二维版
O(N * V);滚动数组/原地优化版O(V)。
代码实现
Python
# 最优化实现:一维 dp + 负无穷初始化 + 可达剪枝(reachCap)
import sys
def knapsack_01_optimized(n, V, vols, vals):
NEG = -10**18 # 表示不可达
dp = [NEG] * (V + 1)
dp[0] = 0
reach = 0 # 当前可达的最大容量
for i in range(n):
v, w = vols[i], vals[i]
if v > V:
continue # 体积超过背包容量的物品直接跳过
end = min(V, reach + v) # 可达剪枝的上界
# 倒序枚举,保证每件物品只用一次
for j in range(end, v - 1, -1):
if dp[j - v] != NEG: # 只有前态可达才尝试转移
cand = dp[j - v] + w
if cand > dp[j]:
dp[j] = cand
reach = end # 更新当前可达的最大容量
# 答案为不超过 V 的最大价值(恰好容量 j 的最大价值中的最大者)
return max(dp)
def main():
data = list(map(int, sys.stdin.read().strip().split()))
N, V = data[0], data[1]
vols, vals = [], []
idx = 2
for _ in range(N):
v, w = data[idx], data[idx + 1]
vols.append(v)
vals.append(w)
idx += 2
print(knapsack_01_optimized(N, V, vols, vals))
if __name__ == "__main__":
main()
Java
// 最优化实现:一维 dp + 负无穷初始化 + 可达剪枝(reachCap)
import java.util.*;
public class Main {
// 外部函数:实现 0/1 背包(最优化版)
static int knapsack01Optimized(int n, int V, int[] vols, int[] vals) {
final int NEG = -1_000_000_000; // 不可达标记(远小于最大可能价值 1e6)
int[] dp = new int[V + 1];
Arrays.fill(dp, NEG);
dp[0] = 0;
int reach = 0; // 当前可达的最大容量
for (int i = 0; i < n; i++) {
int v = vols[i], w = vals[i];
if (v > V) continue; // 无效物品跳过
int end = Math.min(V, reach + v); // 可达剪枝上界
for (int j = end; j >= v; j--) { // 倒序,保证每件物品只用一次
if (dp[j - v] != NEG) {
int cand = dp[j - v] + w;
if (cand > dp[j]) dp[j] = cand;
}
}
reach = end; // 更新可达上界
}
int ans = 0;
for (int j = 0; j <= V; j++) ans = Math.max(ans, dp[j]);
return ans;
}
// 主函数:读取输入并输出结果(ACM 风格)
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt(), V = sc.nextInt();
int[] vols = new int[N], vals = new int[N];
for (int i = 0; i < N; i++) {
vols[i] = sc.nextInt();
vals[i] = sc.nextInt();
}
System.out.println(knapsack01Optimized(N, V, vols, vals));
sc.close();
}
}
C++
// 最优化实现:一维 dp + 负无穷初始化 + 可达剪枝(reachCap)
#include <bits/stdc++.h>
using namespace std;
// 外部函数:实现 0/1 背包(最优化版)
int knapsack01Optimized(int n, int V, const vector<int>& vols, const vector<int>& vals) {
const int NEG = -1000000000; // 不可达标记(足够小)
vector<int> dp(V + 1, NEG);
dp[0] = 0;
int reach = 0; // 当前可达的最大容量
for (int i = 0; i < n; ++i) {
int v = vols[i], w = vals[i];
if (v > V) continue; // 体积超过背包容量的物品跳过
int end = min(V, reach + v); // 可达剪枝上界
// 倒序枚举,避免同一物品重复使用
for (int j = end; j >= v; --j) {
if (dp[j - v] != NEG) {
int cand = dp[j - v] + w;
if (cand > dp[j]) dp[j] = cand;
}
}
reach = end; // 更新可达上界
}
int ans = 0;
for (int j = 0; j <= V; ++j) ans = max(ans, dp[j]);
return ans;
}
// 主函数:读取输入并输出结果(ACM 风格)
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, V;
if (!(cin >> N >> V)) return 0;
vector<int> vols(N), vals(N);
for (int i = 0; i < N; ++i) cin >> vols[i] >> vals[i];
cout << knapsack01Optimized(N, V, vols, vals) << "\n";
return 0;
}
题面描述
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。输出最大价值。
输入格式
- 第一行两个整数 N,V,用空格隔开,分别表示物品数量和背包容量。
- 接下来有 N 行,每行两个整数 vi,wi,用空格隔开,分别表示第 i 件物品的体积和价值。
输出格式
输出一个整数,表示最大价值。
数据范围
- 0<N,V≤1000
- 0<vi,wi≤1000
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例
8