背包问题Java详解版_背包问题及可视化javafx

资料：B站背包九讲：https://www.bilibili.com/video/BV1qt411Z7nE
对应训练题：https://www.acwing.com/problem/

01背包问题

此问题解法来自背包九讲，

未优化

状态：f[i][j]表示前 i 个物品，总体积为 j 的最大价值

所以就有两种方式，选当前物品放入背包和不选当前物品放入背包

即不选当前物品放入背包 :f[i-1][j],直接拿上一个物品的价值即可，体积不变

或者选当前物品放入背包，:f[i-1][j-v[i]]+w[i],需要减去当前物品的体积 再加上当前物品价值

当前i,j即取二者最大值

状态转移：f[i][j] = Math.max(f[i-1][j],f[i-1][j-v[j]]+w[i])

初始条件，f[0][0]=0

具体代码

public class Main {
 public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int[] Value = new int[N+1];
        int[] Weight = new int[N+1];
        //从1开始，0代表背包内容为0时的最大价值
        for(int i = 1;i<=N;i++){
            Weight[i] = sc.nextInt();
            Value[i] = sc.nextInt();
        }
        System.out.println(packageQuestion2(N,M,Weight,Value));

    }
    public static int packageQuestion(int N,int M,int[] Weight,int[] Value){
        // dp状态方程
        int[][] dp = new int[N+1][M+1];
        // dp[i][j]表示前i个物品，体积是j的，最大的总价值
        //遍历所有物品
        for(int i = 1;i<=N;i++){
            // 从0开始遍历背包容量
            for(int j = 0;j<=M;j++){
              //  dp[i][j]表示前i个物品，体积是j的，最大的总价值
                //如果当前背包容量大于等于当前元素的体积，就可以装
                if(j>=Weight[i]){
                    //dp[i-1][j]表示不选当前元素，表示当前容量下前i个元素的价值等于第i-1个元素的价值
                    //dp[i-1][j-Weight[i]]+Value[i]表示选择当前元素，即：当前元素针对当前背包大小的价值等于(背包现容量
                    //-当前元素的体积)的价值加上当前元素的价值，
                    //这里dp[i-1][j-Weight[i]]+Value[i]，为啥要用i-1的原因是，如果用当前i，其实算当前i的时候已经对当前元素进行处理了，
                    //如果用i，会处理两次，用i-1才是处理针对当前层的上一层的最优
                    //上面是通俗一点的解释，真正的解释是：dp状态转移方程 都是由上一层来递推到当前层而不是直接在当前层上处理当前层的信息
                    dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-Weight[i]]+Value[i]);
                }else{
                    //当前背包容量小于当前元素的体积，针对当前元素当前容量不能装，只能是上一个元素的当前容量的价值
                    dp[i][j] = dp[i-1][j];
                }
            }

            //当前循环结束后，dp二维数组所组成的二维矩阵，每一层即每个元素的最后一个元素都是针对于当前元素及之前的最优解
            //所以整体最优解就是矩阵的右下角
        }
        return dp[N][M];
    }
}


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
39
40
41
42
43
44
45
46
47
48
49

空间优化

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int[] Value = new int[N+1];
        int[] Weight = new int[N+1];
        //从1开始，0代表背包内容为0时的最大价值
        for(int i = 1;i<=N;i++){
            Weight[i] = sc.nextInt();
            Value[i] = sc.nextInt();
        }
        System.out.println(packageQuestion2(N,M,Weight,Value));

    }
    //空间优化
     public static int packageQuestion1(int N,int M,int[] Weight,int[] Value){
        //空间优化，即二维改一维，这里只需初始化大小为M+1即可，即背包大小，每一个元素表示当前重量下的最大价值
        int[] dp = new int[M+1];
        //仍然是遍历所有物品
        for(int i = 1;i<=N;i++){
            //这里从最大的背包数量开始遍历
            for(int j = M;j>=Weight[i];j--){
                //因为这里是一维的，如果不选当前元素，则保持不变即可，因为不变即和之前保持一致
                // 如果要加上当前元素，则仍然按照dp[j-Weight[i]]+Value[i]的来，不过dp[j-Weight[i]]一定是上一层的，根据未优化来的话，
                //就是这层的j-Weight[i]还未被修改，所以这里获得的值也一定是上一层的,注意始终只有一层，没修改之前就是上层的
                dp[j] = Math.max(dp[j],dp[j-Weight[i]]+Value[i]);
            }
        }
        //同样，这里得到的右下角也一定是结果
        return dp[M];
    }
}

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
39
40
41
42

完全背包问题

b站上大神讲的实在看不懂，所以找了个简单的，此题解来源于 https://blog.csdn.net/u013885699/article/details/80254961

 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int[] Value = new int[N+1];
        int[] Weight = new int[N+1];
        //从1开始，0代表背包内容为0时的最大价值
        for(int i = 1;i<=N;i++){
            Weight[i] = sc.nextInt();
            Value[i] = sc.nextInt();
        }
        System.out.println(packageQuestion2(N,M,Weight,Value));

    }
public static int packageQuestion2(int N,int M,int[] Weight,int[] Value){
        int[][] dp = new int[N+1][M+1];
        for(int i = 1;i<=N;i++){
            for(int j =0;j<=M;j++){
                //这之前和上面的01背包问题没区别
                //然后这里因为多了无限数量的条件，所以这里要尝试加入可能的所有的物体的数量
                for(int k = 0;k<=M/Weight[i];k++){
                    //如果当前背包容量可以放下当前数量的物品
                    if(j>=k*Weight[i]){
                        //同样，这里两种情况，一种是不加当前值，那就是上一层的值即dp[i-1][j]
                        //要加当前值，由于这里可以无限选，所以要加上可能的所有值即
                        //dp[i-1][j-k*Weight[i]]为上一层的不加上当前物品的值和数量的最大值，最后加上当前物品的值和数量的最大值
                        //即 dp[i][j]表示对在大于等于i之前的元素的容量为j的最大价值
                        dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-k*Weight[i]]+k*Value[i]);
                    }else{
                        dp[i][j] = dp[i][j];
                    }
                }
            }
        }
        return dp[N][M];
    }
}
 
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
39
40
41

这里用 O(n³)的时间复杂度会超时，所以我们需要优化算法
O(n²）时间复杂度
解法来源：https://www.acwing.com/video/945/
还是大神讲得好琢磨琢磨就差不多了

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int[] Value = new int[N+1];
        int[] Weight = new int[N+1];
        //从1开始，0代表背包内容为0时的最大价值
        for(int i = 1;i<=N;i++){
            Weight[i] = sc.nextInt();
            Value[i] = sc.nextInt();
        }
        System.out.println(packageQuestion3(N,M,Weight,Value));

    }
    public static int packageQuestion3(int N,int M,int[] Weight,int[] Value){
        int[][] dp = new int[N+1][M+1];
        for(int i = 1;i<=N;i++){
            for(int j = 1;j<=M;j++){
                dp[i][j] = dp[i-1][j];
                if(j>=Weight[i]){
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-Weight[i]]+Value[i]);
                }
            }
        }
        return  dp[N][M];
    }
    
}
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

为什么可以优化成O(n²)，先看一组数学式子：

01背包问题递推方程是这样的：dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-Height[i]]+Value[i])

因为01背包问题是非黑即白只有两种状态，所以在这两种状态里找最大值即可

而完全背包问题n个物品n个状态，递推方程为：

某状态A： dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-Height[i]]+Value[i],dp[i-1][j-2Height[i]]+2Value[i])…,dp[i-1][j-nHeight[i]]+nValue[i]

另一个状态B:dp[i][j-Height[i]] = Math.max(dp[i-1][j-Height[i]],dp[i-1][j-Height[i]]+Value[i],dp[i-1][j-2Height[i]]+2Value[i]…,dp[i-1][j-n+1Height[i]]+n+1Value[i])

对比上面两式，可以发现B式每一项 k 都比A式 k-1 项的多出了一个Value[i],所以第一式可以写成这个

A = max(dp[i-1][j],B+Value[i]);

即：dp[i][j] = Math.max(dp[i-1][j],dp[i][j-Height[i]]+Value[i]),即通过等式代换将三个for嵌套优化成了两个for
然后做空间优化

public static int packageQuestion4(int N,int M,int[] Weight,int[] Value){
        int[] dp = new int[M+1];
        for(int i = 1;i<=N;i++){
            for(int j = Weight[i];j<=M;j++){
                dp[j] = Math.max(dp[j],dp[j-Weight[i]]+Value[i]);
            }
        }
        return  dp[M];
    }
1
2
3
4
5
6
7
8
9

同样和01背包问题类似，我们只需要一个一维dp数组，我们将背包从大到小遍历，这样就能保证在计算大的那一项时，dp[j-Weight[i]]在当前 层得到的结果一定是还没有被计算过，也就是保留着上一层的计算结果，所以不需要用二维dp来记录每层的最优解，只需要用倒序遍历，针对于上一层的最优解直接可以用一维且未被当前层处理的dp元素来递推，所以这个二维改一维能对算法进一步做空间优化