acwing-3. 完全背包问题

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 w = sc.nextInt();
        
        int[] weight = new int[n+1];
        int[] value = new int[n+1];
        for(int i = 1; i<= n; i++){
            weight[i] = sc.nextInt();
            value[i] = sc.nextInt();
        }
        System.out.print(getMax(n, w, weight, value));
    }
    
    public static int getMax(int n, int w, int[] weight, int[] value){
        int[][] dp = new int[n+1][w+1];
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= w; j++){
                for(int k = 0; k*weight[i] <= j; k++){
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j-k*weight[i]] + k * value[i]);
                }
            }
        }
        return dp[n][w];
    }
}

状态压缩

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
import java.util.*;
class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int w = sc.nextInt();
        
        int[] weight = new int[n+1];
        int[] value = new int[n+1];
        for(int i = 1; i<= n; i++){
            weight[i] = sc.nextInt();
            value[i] = sc.nextInt();
        }
        System.out.print(getMax(n, w, weight, value));
    }
    
    public static int getMax(int n, int w, int[] weight, int[] value){
        int[] dp = new int[w+1];
        for(int i = 1; i <= n; i++){
            for(int j = weight[i]; j <= w; j++){
                   dp[j] = Math.max(dp[j], dp[j-weight[i]] + value[i]);
            }
        }
        return dp[w];
    }
}