动态规划0/1背包问题

一、0/1背包基础

1.1问题描述

有一堆物品（m个），每个物品有对应的重量（weight[i]）和价值（value[i]）；有一个背包，对应容量为n；问题：物品中任选（每个物品只能取一次），容量为m的背包能装物品的最大价值是多少？

1.2 解题步骤

1.2.1 定义dp数组

的值表示从物品0~i中任取，容量为j的背包所能装的最大价值。

1.2.2 递推公式

其中 的值可以从上一个状态推导出来  =>

当前背包容量 >= 当前物品重量的时候，；

当前背包容量 < 当前物品重量，；

1.2.3 初始化

假设由三个物品：0、1、2

背包容量为：0、1、2、3、4

物品对应的重量：value[] = [15, 20, 30]

物品对应的价值：weight[] = [1, 3, 4]

因为递推公式需要借助于上一行的结果，所以需要将第一行的值初始化。

针对本题第一行，如果背包容量大于物品0的重量，即初始化dp[0,j]为value[0]。

针对第一列而言，因为背包的容量为0，所以dp[i,0]都设置为0即可；针对其它行、列，可随意设置，因为在后面的计算中会将其覆盖掉（这里默认为0）。

1.2.4 遍历

理论上来说的遍历顺序由两类：

先遍历物品，后遍历背包

        1.物品顺序遍历，背包顺序遍历 / 背包逆序遍历

背包顺序遍历 ✔

背包逆序遍历  ✔

        2.物品逆序遍历 ❌ ，因为不能从后往前推结果。

先遍历背包，后遍历物品

        3.背包逆序遍历 ❌，因为不能从后往前推结果。

        4.背包顺序遍历，物品顺序遍历 / 物品逆序遍历

物品顺序遍历 ✔

物品逆序遍历 ❌

1.2.5 打印排查错误

通过打印最后生成的dp数组验证与自己定义的dp是否保持一致！

二、0/1背包代码

1、先物品再背包，物品顺序，背包顺序

import java.util.*;

public class main {
    
    public static void main(string[] args) {
        // 背包容量 n
        // 物品种类 m
        scanner sc = new scanner(system.in);
        
        int m = sc.nextint();
        int n = sc.nextint();
        
        int[] values = new int[m];
        int[] weights = new int[m];
        
        for(int i = 0; i < m;i++) {
            weights[i] = sc.nextint();
        }
        
        
        for(int i = 0; i < m;i++) {
            values[i] = sc.nextint();
        }
        
        int[][] dp = new int[m][n+1];
        
        // 初始化
        // 第一行
        for(int i = 1; i <= n; i++) {
            if(i >= weights[0]){
                dp[0][i] = values[0];
            }
        }
        // 第一列，默认都是0
        
        // 先物品
        for(int i = 1; i < m; i++) {
            // 后背包
            for(int j = 0; j <= n; j++) {
                if(weights[i] > j) {
                    dp[i][j] = dp[i-1][j];
                } else {
                    dp[i][j] = math.max(dp[i-1][j],dp[i-1][j-weights[i]] + values[i]);
                }
            }
        }
        system.out.println(dp[m-1][n]);
    }
}

2、先物品再背包，物品顺序，背包逆序

import java.util.*;

public class main {
    
    public static void main(string[] args) {
        // 背包容量 n
        // 物品种类 m
        scanner sc = new scanner(system.in);
        
        int m = sc.nextint();
        int n = sc.nextint();
        
        int[] values = new int[m];
        int[] weights = new int[m];
        
        for(int i = 0; i < m;i++) {
            weights[i] = sc.nextint();
        }
        
        
        for(int i = 0; i < m;i++) {
            values[i] = sc.nextint();
        }
        
        int[][] dp = new int[m][n+1];
        
        // 初始化
        // 第一行
        for(int i = 1; i <= n; i++) {
            if(i >= weights[0]){
                dp[0][i] = values[0];
            }
        }
        // 第一列，默认都是0
        
        // 先物品
        for(int i = 1; i < m; i++) {
            // 后背包
            for(int j = n; j >= 0; j--) {
                if(weights[i] > j) {
                    dp[i][j] = dp[i-1][j];
                } else {
                    dp[i][j] = math.max(dp[i-1][j],dp[i-1][j-weights[i]] + values[i]);
                }
            }
        }
        system.out.println(dp[m-1][n]);
    }
}

3、先背包再物品，背包顺序，物品顺序

import java.util.*;

public class main {
    
    public static void main(string[] args) {
        // 背包容量 n
        // 物品种类 m
        scanner sc = new scanner(system.in);
        
        int m = sc.nextint();
        int n = sc.nextint();
        
        int[] values = new int[m];
        int[] weights = new int[m];
        
        for(int i = 0; i < m;i++) {
            weights[i] = sc.nextint();
        }
        
        
        for(int i = 0; i < m;i++) {
            values[i] = sc.nextint();
        }
        
        int[][] dp = new int[m][n+1];
        
        // 初始化
        // 第一行
        for(int i = 1; i <= n; i++) {
            if(i >= weights[0]){
                dp[0][i] = values[0];
            }
        }
        // 第一列，默认都是0
        
        // 先背包
        for(int j = 1; j <= n; j++) {
            // 后物品
            for(int i = 1; i < m; i++) {
                if(weights[i] > j) {
                    dp[i][j] = dp[i-1][j];
                } else {
                    dp[i][j] = math.max(dp[i-1][j],dp[i-1][j-weights[i]] + values[i]);
                }
            }
        }
        system.out.println(dp[m-1][n]);
    }
}

三、0/1背包空间优化

因为当前层的数值来源于上一层的结果，所以可以进行空间的优化，且顺序固定，先物品后背包，且物品顺序遍历，背包逆序遍历。背包逆序的原因是因为，只有一维数组，物品顺序遍历结果会将上一层的结果覆盖，导致后面的新的计算结果出现错误。

代码：

import java.util.*;

public class main {
    
    public static void main(string[] args) {
        // 背包容量 n
        // 物品种类 m
        scanner sc = new scanner(system.in);
        
        int m = sc.nextint();
        int n = sc.nextint();
        
        int[] values = new int[m];
        int[] weights = new int[m];
        
        // 对应物品的重量
        for(int i = 0; i < m;i++) {
            weights[i] = sc.nextint();
        }
        
        
        // 对应物品的价值
        for(int i = 0; i < m;i++) {
            values[i] = sc.nextint();
        }
        
        int[] dp = new int[n+1];  // 一维dp表示背包容量为j，所能装的最大价值
        
        // 初始化,都是0
        
        // 遍历 -> 先物品后背包 -> 且背包倒叙遍历
        for(int i = 0;i < m;i++){
            for(int j = n;j >= 1;j--){
                // 滚动起来
                if(j >= weights[i]){
                    dp[j] = math.max(dp[j], dp[j - weights[i]] + values[i]);
                }
            }
            
        }
        
        system.out.println(dp[n]);
    }
}

四、参考链接

代码随想录

卡码网kamacoder