背包九讲

 1 import java.util.*;
 2 
 3 public class Main {
 4     public static void main(String[] args) {
 5         Scanner sc = new Scanner(System.in);
 6         int N = sc.nextInt();
 7         int V = sc.nextInt();
 8         int[] v = new int[N + 1];
 9         int[] w = new int[N + 1];
10         for (int i = 1; i <= N; i++) {
11             v[i] = sc.nextInt();
12             w[i] = sc.nextInt();
13         }
14         int res = helper2(N, V, v, w);
15         System.out.println(res);
16     }
17 
18     /**
19      * dp[i][j] 表示前i个物品，在最大体积为j的时候的最大值
20      * dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - v[i]] + w[i])
21      */
22     private static int helper(int N, int V, int[] v, int[] w) {
23         int[][] dp = new int[N + 1][V + 1];
24 
25         for (int i = 1; i <= N; i++) {
26             for (int j = 0; j <= V; j++) {
27                 if (j - v[i] >= 0) {
28                     dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);
29                 } else {
30                     dp[i][j] = dp[i - 1][j];
31                 }
32             }
33         }
34         return dp[N][V];
35     }
36 
37     /**
38      * 由于二维数组之后只有一维有用，可以压缩
39      * dp[j]表示体积为j的情况下最大的价值
40      * 要从大到小循环，因为要用未覆盖的值
41      */
42     private static int helper2(int N, int V, int[] v, int[] w) {
43         int[] dp = new int[V + 1];
44 
45         for (int i = 1; i <= N; i++) {
46             for (int j = V; j >= v[i]; j--) {
47                 dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
48             }
49         }
50         return dp[V];
51     }
52 }