题解 | #【模板】01背包#
【模板】01背包
https://www.nowcoder.com/practice/fd55637d3f24484e96dad9e992d3f62e
纯二维i数组解法：
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
int n = in.nextInt();
int limit = in.nextInt();
int[] items = new int[n];
int[] values = new int[n];
for (int i=0;i<n;i++){
items[i] = in.nextInt();
values[i] = in.nextInt();
}
int[][] dp1 = new int[n+1][limit+1];
for (int i=0;i<n;i++){
dp1[i][0] = 0;
}
for (int i=1;i<=n;i++){
for (int j=1;j<=limit;j++){
if (j<items[i-1]) dp1[i][j] = dp1[i-1][j];
else dp1[i][j] = Math.max(dp1[i-1][j],dp1[i-1][j-items[i-1]]+values[i-1]);
}
}
int[][] dp2 = new int[n+1][limit+1];
Arrays.fill(dp2[0],Integer.MIN_VALUE);
for (int i=0;i<=n;i++){
dp2[i][0] = 0;
}
for (int i=1;i<=n;i++){
for (int j=1;j<=limit;j++){
if (j<items[i-1]) dp2[i][j] = dp2[i-1][j];
else dp2[i][j] = Math.max(dp2[i-1][j],dp2[i-1][j-items[i-1]]+values[i-1]);
}
}
System.out.println(dp1[n][limit]);
System.out.println(dp2[n][limit]>0?dp2[n][limit]:0);
}
}
