AcWing 2. 01背包问题
原题链接
简单
作者:
fourth_nt
,
2024-03-27 19:55:33
,
所有人可见
,
阅读 1
Java代码
import java.util.Scanner;
public class Main {
//二维
//状态表示:dp[i][j],在背包容量为j,物体数量为i的情况下的最大价值。因为最大价值不止和物体i有关,还与当前背包容量相关,所以没有直接使用dp[i]当作当前状态
//在背包容量够的情况下有两种状态:选择i/不选
//选:dp[i][j] = dp[i - 1][j - v[i]] + w[i]
//不选:dp[i][j] = dp[i - 1][j]
//容量不够:dp[i][j] = dp[i - 1][j]
//一维(使用滚动数组),第i行元素只由i - 1行得到,可以优化成一维
//状态表示:f[j],N件物品在背包容量为j的最大价值
//两种状态:选i/不选
//选:f[j] = f[j];不选:f[j] = f[j - w[i]] + v[i]
//j需要倒序遍历
public static void main(String[] args) {
//数据输入
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
int V = scanner.nextInt();
int[] dp = new int[V + 2];
for(int i = 1; i <= N; i++) {
int v = scanner.nextInt(), w = scanner.nextInt();
for(int j = V; j >= v; j--) {
dp[j] = Math.max(dp[j], dp[j - v] + w);
}
}
System.out.print(dp[V]);
}
}