题解 | 【模板】01背包
【模板】01背包
https://www.nowcoder.com/practice/fd55637d3f24484e96dad9e992d3f62e
解题思路
-
问题分析：
- 第一问：求背包能装下的最大价值（不要求装满）
- 第二问：求背包恰好装满时的最大价值（要求装满）
-
状态定义：
：容量为
时能装下的最大价值（不要求装满）
：容量为
-
初始化：
全部初始化为
（表示空背包，价值为
除了
外，其他都初始化为负无穷（表示还未找到恰好装满的方案）
-
状态转移：
对每个物品 :
对每个容量
从
到
：
// 不要求装满
// 要求装满
-
结果获取：
- 第一问：直接输出
- 第二问：如果
为负无穷，输出
- 第一问：直接输出
-
优化方案：
- 使用滚动数组（一维dp）节省空间
- 从后向前遍历避免重复使用物品
- 使用
long long类型避免整数溢出
代码
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int main() {
int n, V;
cin >> n >> V;
// 不要求装满的dp数组
vector<long long> dp1(V + 1, 0);
// 恰好装满的dp数组
vector<long long> dp2(V + 1, LLONG_MIN);
dp2[0] = 0;
for(int i = 0; i < n; i++) {
int v, w;
cin >> v >> w;
// 从后向前遍历避免重复使用
for(int j = V; j >= v; j--) {
if(dp1[j-v] != LLONG_MIN)
dp1[j] = max(dp1[j], dp1[j-v] + w);
if(dp2[j-v] != LLONG_MIN)
dp2[j] = max(dp2[j], dp2[j-v] + w);
}
}
cout << dp1[V] << endl;
cout << (dp2[V] == LLONG_MIN ? 0 : dp2[V]) << endl;
return 0;
}
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int V = sc.nextInt();
// 不要求装满的dp数组
long[] dp1 = new long[V + 1];
// 恰好装满的dp数组
long[] dp2 = new long[V + 1];
Arrays.fill(dp2, Long.MIN_VALUE);
dp2[0] = 0;
for(int i = 0; i < n; i++) {
int v = sc.nextInt();
int w = sc.nextInt();
// 从后向前遍历避免重复使用
for(int j = V; j >= v; j--) {
if(dp1[j-v] != Long.MIN_VALUE)
dp1[j] = Math.max(dp1[j], dp1[j-v] + w);
if(dp2[j-v] != Long.MIN_VALUE)
dp2[j] = Math.max(dp2[j], dp2[j-v] + w);
}
}
System.out.println(dp1[V]);
System.out.println(dp2[V] == Long.MIN_VALUE ? 0 : dp2[V]);
sc.close();
}
}
def solve_knapsack():
n, V = map(int, input().split())
# 不要求装满的dp数组
dp1 = [0] * (V + 1)
# 恰好装满的dp数组
dp2 = [-float('inf')] * (V + 1)
dp2[0] = 0
for _ in range(n):
v, w = map(int, input().split())
# 从后向前遍历避免重复使用
for j in range(V, v - 1, -1):
if dp1[j-v] != -float('inf'):
dp1[j] = max(dp1[j], dp1[j-v] + w)
if dp2[j-v] != -float('inf'):
dp2[j] = max(dp2[j], dp2[j-v] + w)
print(dp1[V])
print(dp2[V] if dp2[V] != -float('inf') else 0)
if __name__ == "__main__":
solve_knapsack()
算法及复杂度
- 算法：动态规划（01背包）
- 时间复杂度：
，
是物品数量，
是背包容量
- 空间复杂度：
，使用滚动数组优化
查看15道真题和解析
