import java.util.Scanner;
//全局变量 -> 定义到堆里面 -> 都会被初始化为0
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int v[] = new int [n+1];
int w[] = new int [n+1];
for(int i = 1 ; i <= n ; i++) {
w[i] = sc.nextInt();
v[i] = sc.nextInt();
}
System.out.println(zore_one_knapsack(v,w,n,m));
}
public static int zore_one_knapsack(int v[] , int w[] ,int n ,int m ) {
int flag[][] = new int [n+1][m+1];
for(int i = 1 ; i <= n ; i ++) {
for(int j = 1 ; j <= m ; j ++) {
if(j < w[i])
flag[i][j] = flag[i-1][j]; //有空间就选 因为是前i个有空间只能选
else { // 没有空间就看不选第i件物品的价值,跟选了第i件物品的价值[得空出j-w[i]的空间]
int value1 = flag[i-1][j-w[i]] + v[i];
int value2 = flag[i-1][j];
flag[i][j] = Math.max(value1 , value2);
}
}
}
return flag[n][m];
}
}
大佬,图很详细。
感谢感谢,背包问题有点懂了。