01背包和完全背包

01背包

题目介绍

有 N 件物品和一个容量为 V 的背包，每件物品有各自的价值且只能被选择一次，要求在有限的背包容量下，使装入的物品总价值最大

代码

参考文章：AcWing 2. 01背包问题（状态转移方程讲解） - AcWing

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
32
33
34
35
36
37
38
import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int N=s.nextInt();
        int V=s.nextInt();
        int[] v=new int[N+1];
        int[] w=new int[N+1];
        for (int i=1;i<=N;i++){
            v[i]=s.nextInt();
            w[i]=s.nextInt();
        }
        s.close();
        
        //二维数组解决
        // int[][] dp=new int[N+1][V+1];
        // for (int i = 1; i <= N; i++) {
        //     for (int j = 0; j <= V; j++) {
        //         if (j>=v[i]){
        //             dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);
        //         }else {
        //             dp[i][j]=dp[i-1][j];
        //         }
        //     }
        // }
        // System.out.println(dp[N][V]);
        
        //一维数组解决
        int[] dp=new int[V+1];
        for(int i=1;i<=N;i++){
            for(int j=V;j>=v[i];j--){
                dp[j]=Math.max(dp[j],dp[j-v[i]]+w[i]);
            }
        }
        System.out.println(dp[V]);
    }
}

完全背包

题目介绍

有 N 件物品和一个容量为 V 的背包，每件物品有各自的价值且都有无限件可用，要求在有限的背包容量下，使装入的物品总价值最大

代码

参考文章：AcWing 3. 完全背包问题 - AcWing

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
32
33
34
35
import java.util.Scanner;
public class Main{
    public static void main(String[] args)throws Exception{
        Scanner s=new Scanner(System.in);
        int N=s.nextInt();
        int V=s.nextInt();
        int[] v=new int[N+1];
        int[] w=new int[N+1];
        for(int i=1;i<=N;i++){
            v[i]=s.nextInt();
            w[i]=s.nextInt();
        }
        s.close();
        
        //二维数组解决
        // int[][] dp=new int[N+1][V+1];
        // for(int i=1;i<=N;i++){
        //     for(int j=0;j<=V;j++){
        //         for(int k=0;k*v[i]<=j;k++){
        //             dp[i][j]=Math.max(dp[i][j],dp[i-1][j-k*v[i]]+k*w[i]);
        //         }
        //     }
        // }
        // System.out.println(dp[N][V]);
        
        //一维数组解决
        int[] dp=new int[V+1];
        for(int i=1;i<=N;i++){
            for(int j=v[i];j<=V;j++){
                dp[j]=Math.max(dp[j],dp[j-v[i]]+w[i]);
            }
        }
        System.out.println(dp[V]);
    } 
}

背记

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int[] dp=new int[V+1];

//01背包
for(int i=1;i<=N;i++){
    for(int j=V;j>=v[i];j--){
        dp[j]=Math.max(dp[j],dp[j-v[i]]+w[i]);
    }
}
//完全背包
for(int i=1;i<=N;i++){
    for(int j=v[i];j<=V;j++){
        dp[j]=Math.max(dp[j],dp[j-v[i]]+w[i]);
    }
}

System.out.println(dp[V]);