acwing-2. 01背包问题

二维数组dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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[] value = new int[N + 1];
        for(int i = 1; i<= N; i++){
            w[i] = sc.nextInt();
            value[i] = sc.nextInt();
        }
        int res = getMaxValue(N, w, value, V);
        System.out.print(res);
    }
    
    public static int getMaxValue(int n, int[] w, int[] value, int V){
        // dp中存的是最大价值
        int[][] dp = new int[n + 1][V + 1];
        
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= V; j++){
                dp[i][j] = dp[i-1][j];
                if(j >= w[i]){
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j-w[i]] + value[i]);
                }
            }
        }
        return dp[n][V];
    }
}

滚动数组压缩

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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[] value = new int[N + 1];
        for(int i = 1; i<= N; i++){
            w[i] = sc.nextInt();
            value[i] = sc.nextInt();
        }
        int res = getMaxValue(N, w, value, V);
        System.out.print(res);
    }
    
    public static int getMaxValue(int n, int[] w, int[] value, int V){
        // dp中存的是最大价值
        int[] dp = new int[V + 1];
        
        for(int i = 1; i <= n; i++){
            for(int j = V; j >= w[i]; j--){
            	dp[j] = Math.max(dp[j], dp[j-w[i]] + value[i]);
            }
        }
        return dp[V];
    }
}