AcWing 2. 01背包问题
原题链接
简单
作者:
Demo_5
,
2023-11-12 17:36:35
,
所有人可见
,
阅读 47
算法1
二维动态规划 代码
import java.util.*;
class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int V = sc.nextInt();
int[] w = new int[N+1];
int[] v = new int[N+1];
for(int i = 1;i <= N;i++){
w[i] = sc.nextInt();
v[i] = sc.nextInt();
}
//表示前i个物品,体积为j时,可以装的最大值
int[][] f = new int[N+1][V+1];
for(int i = 1;i <= N;i++){
for(int j = 1;j <= V;j++){
f[i][j] = f[i-1][j];
if(j - w[i] >= 0)f[i][j] = Math.max(f[i][j],f[i-1][j-w[i]]+v[i]);
}
}
System.out.println(f[N][V]);
}
}
一维动态规划 代码
import java.util.*;
class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int V = sc.nextInt();
int[] w = new int[N+1];
int[] v = new int[N+1];
for(int i = 1;i <= N;i++){
w[i] = sc.nextInt();
v[i] = sc.nextInt();
}
int[] f = new int[V+1];
for(int i = 1;i <= N;i++)
//本次的数据是根据上一次的数据更新的,因此需要从后往前更新
for(int j = V;j >= w[i];j--)
f[j] = Math.max(f[j],f[j-w[i]]+v[i]);
System.out.println(f[V]);
}
}