动态规划之背包问题。

讲解背包问题最经典的当属《背包九讲》，之前看了前面一点点，现在又忘了，所以还是的写笔记

面试需要，不做太深入的了解。这里仅学习零一背包、完全背包和多重背包问题

[1] 参考了背包九讲背包九讲就是讲背包的永远滴神

1 背包问题介绍

1.1 背包问题的基本描述和分类

背包问题的基本描述：有N件物品和一个最多能装重量为W 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。

01背包：每种物品仅有一件，可以选择放或不放。求解将哪些物品装入背包可使价值总和最大。
完全背包：每种物品都有无限件可用，求解将哪些物品装入背包可使价值总和最大。
多重背包：每件物品的数量由nums[i]表示，求解价值总和最大的装法。

1.2 背包问题的基本解法（01背包为例）

就是动态规划，但不同问题，遍历计算的顺序大不相同。

动态规划的三大要点：1状态 2确定初始化和重点 3列出状态转移方程

为什么要用动态规划？

一个物品存在选择或者不选择两种情况，暴力解法就是2^n种选择。显然需要用动态规划保存状态来降低时间复杂度。

基础的01背包案例：背包容量为n、一共有m个物品，物品重量数组W[1:m]，价值数组V[1:m]

状态dp[i][j]表示从前i个的物品种任意取，放进容量为j的背包，能获得的最大价值总和
初始化状态和终点
- dp[i][0]=0（容量为0的背包取出的价值为0）dp[0][j]=0 （没有任何物品取出价值为0）
- dp[i][j]=dp[i-1][j]（因为多一个物品一定比少一个物品获得可能的结果更大，所以可以用上一个状态表示初始值）
- 终点：dp[m][n] 一共有m个物品，背包容量为n
状态转移方程
- 若(j-W[i-1]>0),就表示W[i-1]元素可以作为填充背包的一部分，即
- dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-W[i-1]]+V[i-1]);

public int backPack01(int m, int[] W, int[] V) {
    //dp[i][j]表示将前i个元素的组合、装入容量为j的背包 能获得的最大价值
    //显然dp[i][j]的值一定大于等于dp[i-1][j]，可以所谓基础值
    //初始化 dp[..][0] = 0;
    //终点 dp[n][m]
    //动态迭代
    //先令dp[i][j]=dp[i-1][j],,若(j-W[i-1]>0),就表示W[i-1]元素可以作为填充背包的一部分，则
    //dp[i][j] = max(dp[i-1][j],dp[i-1][j-W[i-1]]+V[i-1]);
    int n = A.length;
    int[][] dp = new int[n+1][m+1];
    for(int i =1;i<=n;++i){
        for(int j=0;j<=m;++j){
            dp[i][j]=dp[i-1][j];
            if(j-W[i-1]>=0){
                dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-W[i-1]]+V[i-1]);
            }
        }
    }
    return dp[n][m];
}

由遍历过程我们可以知道，dp[i][j]层都是由dp[i-1][j]层推导过来的，其实可以只使用一维数组保存状态。

要注意到，此时j的循环必须是从大到小的逆序循环！！因为dp[i][j]是由dp[i-1][j] dp[i-1][j-w[i-1]]推导而来，，每次求j的位置的值用到了j位置和j之前位置的元素！！！

代码如下，不再赘述：

public int backPack01(int m, int[] W, int[] V) {
    int[] dp = new int[m+1];//表示容量为j的背包的最大价值和
    int n = W.length;
    for(int i=1;i<=n;i++){
        for(int j=m; j>=0;j--){
            if(j-W[i-1]>=0) dp[j] = Math.max(dp[j],dp[j-W[i-1]]+V[i-1]);
        }
    }
    return dp[m];
}

2 01背包题解

了解概念之后、直接刷题学习

0/1背包类型：5m、53e、55m、62m、70e、91m、121e、139m、152m、198m、 213m、300m、303e、309m、322m、338m、377m、416m、647m、673m、698m

416 1049 494 474

92 · 背包问题

在n个物品中挑选若干物品装入背包，最多能装多满？假设背包的大小为m，每个物品的大小为A[i]

思路：dp[i][j] 表示使用前i个物品最多能将容量为j的背包装的容量大小

初始化dp[i][0]=0 dp[0][j]=0 dp[i][j] = dp[i-1][j]
迭代方程if(j>A[i-1]) dp[i][j] = dp[i-1][j-A[i-1]]+A[i-1]

代码：

public class Solution {
    public int backPack(int m, int[] A) {
        // `dp[i][j]` 表示使用前`i`个物品最多能将容量为`j`的背包装的容量大小
        int n = A.length;
        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>=A[i-1]) dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-A[i-1]]+A[i-1]);
            }
        }
        return dp[n][m];
    }
}

416. 分割等和子集

给你一个只包含正整数的非空数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

思路：做这道题需要做一个等价转换：两子集元素和相等即表示：是否可以从输入数组中挑选出一些正整数，使得这些数的和等于整个数组元素的和的一半。

所以题目变成了，是否可以挑出一些数来是他们的和等于sum/2。挑选的过程就类似与背包选择的过程。经典的背包问题是能装多满、这里问的是是否刚好等于，所以状态数组dp[][]是boolean类型的

状态dp[i][j] 表示使用前i个元素，是否存在一个组合使其和为j
- i从0到n-1，，j从0到target
初始化 dp[i][0]=false; dp[0][j]=true(if nums[0]==j) ;dp[i][j] = dp[i - 1][j]
终点 dp[n-1][sum/2];
动态迭代 if(j-nums[i]>=0 && dp[i-1][j-nums[i]]) dp[i][j] = true;

依然可以看到dp[i][j] = dp[i - 1][j]类似的初始化，因为多一个元素一定比少一个元素的结果更理想，

然后动态迭代时，同样也用到了dp[i-1][j-nums[i]] 之前的状态，即使用nums[i]和不使用nums[i]存在明显的先后关系！！

代码：细节挺多的，不容易ak

class Solution {
    public boolean canPartition(int[] nums) {
        //dp[i][j]表示前i个数是否能组合出j的整数和
        //目标值target就是sum的一半
        int n = nums.length;
        int sum = 0;
        for(int i=0;i<n;i++) sum+=nums[i];
        if(sum%2!=0) return false;
        int target = sum/2;
        boolean[][] dp = new boolean[n][target+1];
        //初始化
        for(int i=0;i<n;i++) dp[i][0] = false; //可写可不写
        //0个数一定组合不出来什么 这样的初始状态无意义 所以要从1个数开始
        if(nums[0]<=target) dp[0][nums[0]] = true; //这里的判断别忘记加
        //for(int j=0;j<=target;j++) dp[0][j] = nums[0]==j? true:false;

        for(int i=1;i<n;i++){
            for(int j=1;j<=target;j++){
                dp[i][j] = dp[i-1][j];
                if(j-nums[i]>=0 && dp[i-1][j-nums[i]]) dp[i][j] = true ; 
                //这里必须这么写 防止把true变为了false
            }
        }
        return dp[n-1][target];
    }
}

494. 目标和

给你一个整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 ‘+’ 或 ‘-‘ ，然后串联起所有整数，可以构造一个表达式：

例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-‘ ，然后串联起来得到表达式 “+2-1” 。
返回可以通过上述方法构造的、运算结果等于 target 的不同表达式的数目。

输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

下意识看到觉得好难，然后思路是回溯….

方法一：回溯法（为什么不需要用for循环呢？)

class Solution {
    int count = 0;
    int sumIndex = 0;
    public int findTargetSumWays(int[] nums, int target) {
        //自己再尝试一下回溯写法
        backtrack(nums,target,0);
        return count;
    }
    private void backtrack(int[] nums, int target, int index){
        if(index==nums.length) {
            if(sumIndex == target) count++;
            return;
        }
        //做加法的选择
        sumIndex += nums[index];
        backtrack(nums,target,index+1);
        sumIndex -= nums[index];

        //做减法的选择
        sumIndex -= nums[index];
        backtrack(nums,target,index+1);
        sumIndex +=nums[index];
    }
}

方法二：递归

class Solution {
    int count;
    public int findTargetSumWays(int[] nums, int target) {
        //还是先写一遍递归的吧 最适合面试A
        helper(0,0,nums,target);
        return count;
    }
    private void helper(int index, int SumIndex, int[] nums, int target){
        if(index>=nums.length){
            if(SumIndex==target) count++;
        }else{
            helper(index+1,SumIndex+nums[index], nums,target);
            helper(index+1,SumIndex-nums[index],nums,target);
        }
    }
}

方法三：动态规划（01背包问题）

思路：看起来不像01背包、但其实就是01背包

dp[i][j] 表示前i个元素可以组成j值的组合数目
动态规划问题，建议先考虑迭代方程（这样你才知道需要初始化哪些位置：因为不一定总是第1行第1列）
dp[i][j] = dp[i-1][j-nums[i]] + dp[i-1][j+nums[i]] //总是由上一行推导这一行，所以初始化第一行就ok
dp[0][j] //第一个元素组合出j的种数，，那就是dp[0][nums[i]] += 1; dp[0][-nums[i]] += 1; 就完事！！注意用+=因为这两个可能是同一个位置！！
最后因为j可能为负数，且范围是[-1000,1000], 所以j索引的位置总是+1000，使索引非负

代码：

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        //dp[i][j] 表示前i个元素可以组成j值的组合数目
        int m = nums.length; int n = 2001;
        int[][] dp = new int[m][n];
        //初始化
        dp[0][nums[0]+1000] += 1;
        dp[0][-nums[0]+1000] += 1;
        for(int i=1;i<m;i++){
            for(int j=-1000;j<=1000;j++){
                if(j-nums[i]+1000>=0) dp[i][j+1000] += dp[i-1][j-nums[i]+1000]; 
                if(j+nums[i]+1000<=2000) dp[i][j+1000] += dp[i-1][j+nums[i]+1000]; 
                //if(j==0) System.out.println(dp[i][j+1000]);
            }
        }
        return dp[m-1][target+1000];
    }
}

为什么说他是零一背包的问题呢？因为都是由上一行的状态推导这一行，并且推导过程需要减去（加上）nums[i]

dp[i][j] += dp[i-1][j-nums[i]]
dp[i][j] += dp[i-1][j+nums[i]]

474. 一和零

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的大小，该子集中最多有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的子集。

输入：strs = [“10”, “0001”, “111001”, “1”, “0”], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {“10”,”0001”,”1”,”0”} ，因此答案是 4 。
其他满足题意但较小的子集包括 {“0001”,”1”} 和 {“10”,”1”,”0”} 。{“111001”} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。

思路：就是多了一维的01背包问题

dp[i][j][k] 表示前i索引的字符串满足0的个数<=j && 1的个数<=k的最大子集的大小
dp[i][j][k] = dp[i-1][k][j]; dp[i][j][k] = dp[i-1][j-a][k-b]+1 a、b分别表示strs[i]中0和1的个数
初始化：01背包问题都是有上一行推导下一行、所以只用初始化第一行dp[0][j][k] =1 if(j>=a&&k>=b)

代码：其实代码简单、就是不容易想到是01背包问题…

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        //恐怖如斯，，我思路和题解完全一致..多了一维的01背包问题
        //dp[i][j][k] 表示前i索引的字符串 满足0的个数<=j && 1的个数<=k的最大子集的大小
        int len = strs.length;
        int[][][] dp = new int[len][m+1][n+1];
        int[] temp = getCount(strs[0]);
        for(int j=m;j>=temp[0];j--){
            for(int k=n;k>=temp[1];k--){
                dp[0][j][k]=1;
            }
        }
        for(int i=1;i<len;i++){
            for(int j=0;j<=m;j++){
                for(int k=0;k<=n;k++){
                    dp[i][j][k] = dp[i-1][j][k];
                    temp = getCount(strs[i]);
                    if(temp[0]<=j&&temp[1]<=k) dp[i][j][k] = Math.max(dp[i][j][k], dp[i-1][j-temp[0]][k-temp[1]]+1);
                }
            }
        }
        return dp[len-1][m][n];
    }

    private int[] getCount(String s){
        int a = 0, b=0;
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='0') a++;
            else b++;
        }
        return new int[]{a,b};
    }
}

3 完全背包题解

518 377 322 279 139

70 爬楼梯是完全背包？我不会写了

440 · 背包问题 III

给定 n 种物品, 每种物品都有无限个. 第 i 个物品的体积为 A[i], 价值为 V[i].

再给定一个容量为 m 的背包. 问可以装入背包的最大价值是多少?

样例 1:
1
2
3
输入: A = [2, 3, 5, 7], V = [1, 5, 2, 4], m = 10
输出: 15
解释: 装入三个物品 1 (A[1] = 3, V[1] = 5), 总价值 15.

思路一：先来一个01背包的解法。（01生万物）

完全背包问题，三层循环
dp[i][j]表示前i索引物品任意取，背包容量为j时的最大价值

动态迭代 第`i`索引物品最多使用的个数是 `m/A[i]`   所以次数`k`取0到`m/A[i]`

``dp[i][j] = max(dp[i][j], dp[i-1][j-kA[i-1]]+kV[i-1])`
初始化 dp[0][j]=j/A[0]*A[0]; dp[i][j]=dp[i-1][j] 终点dp[n-1][m]

代码：

public class Solution {
    public int backPackIII(int[] A, int[] V, int m) {
        // 完全背包问题，三层循环
        // dp[i][j]表示前i索引物品任意取，背包容量为j时的最大价值
        int n = A.length;
        if(n<=0) return 0;
        int[][] dp = new int[n][m+1];
        //初始化
        for(int j = 0;j<=m;j++) dp[0][j] = j/A[0]*A[0];
        //动态迭代
        for(int i= 1;i<n;i++){
            for(int j=0;j<=m;j++){
                dp[i][j] = dp[i-1][j];
                for(int k =0;k<=m/A[i];k++){
                    if(j-k*A[i]>=0)
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j-k*A[i]]+k*V[i] );
                }
            }
        }
        return dp[n-1][m];
    }
}

思考：

dp[i][j]=dp[i-1][j] 同样采用了多用一个元素一定比少用一个元素结果更理想的01背包思想！！
动态迭代方程采用dp[i-1][j-k*A[i]]+k*V[i]，表示在上一行的选择基础上、选择k个A[i]元素的价值，，取其中的最大值就好了。就是多了一层k循环的01背包问题

思路二：对于时间问题的简化

01背包问题是每个物品只能选一次、所以我们只能在上一行未选择A[i]这个元素的基础上继续做选择（选或者不选），，，而完全背包的问题是A[i]这个元素可以选择任意次，所以我们可以直接在本行已选择A[i]的基础上继续选择！！！，这就是完全背包和01背包最根本的区别，所需的改动也仅仅是动态方程中从上行[i-1]选还是从本行[i]选

一旦我们从本行选择、就无需每次都遍历k次，直接减少一层循环！！因为本行的dp[i][j]用到了本行的dp[i][j-A[i]]所以，j一定过要从小到大遍历！！

dp[i][j]表示前i索引物品任意取，背包容量为j时的最大价值
动态迭代： dp[i][j] = max(dp[i][j], dp[i][j-k*A[i-1]]+k*V[i-1])
注意因为 dp[i][j]用到了dp[i][j-k*A[i-1]]，所以j的循环要从小到大
初始化 dp[0][j]=j/A[0]*A[0]; dp[i][j]=dp[i-1][j] 终点dp[n-1][m]

代码：

public class Solution {
    public int backPackIII(int[] A, int[] V, int m) {
        // 方法二：完全背包问题的时间优化
        // dp[i][j]表示前i索引物品任意取，背包容量为j时的最大价值
        int n = A.length;
        if(n<=0) return 0;
        int[][] dp = new int[n][m+1];
        //初始化
        for(int j = 0;j<=m;j++) dp[0][j] = j/A[0]*A[0];
        //动态迭代
        for(int i= 1;i<n;i++){
            for(int j=0;j<=m;j++){
                dp[i][j] = dp[i-1][j];
                    if(j-A[i]>=0)
                    dp[i][j] = Math.max(dp[i][j], dp[i][j-A[i]]+V[i] );
            }
        }
        return dp[n-1][m];
    }
}

思路三：进一步对空间问题的简化

因为求本行的数据只用到了上一行j位置的数据，和本行j之前的数据，所以一维数组就可以(和01背包的空间优化是一个思路)

dp[j]表示示前i个物品任意取，背包容量为j时的最大价值
动态迭代 j从0迭代到m，，i还是从1迭代到n，，O(mn)时间复杂度
dp[j] = Math.max(dp[j], dp[j-A[i]]+V[i]);
初始化 dp[j]== j/A[0]*A[0]; 终点dp[m]

代码：

public class Solution {
    public int backPackIII(int[] A, int[] V, int m) {
        //方法三：完全背包 时间空间都优化
        //dp[j]表示示前i个物品任意取，背包容量为j时的最大价值
        int n = A.length;
        if(n<=0) return 0;
        int[] dp = new int[m+1];
        //初始化
        for(int j = 0;j<=m;j++) dp[j] = j/A[0]*A[0];
        //动态迭代
        for(int i=1;i<n;i++){
            for(int j=0;j<=m;j++){
                //dp[j] = dp[j];
                if(j-A[i]>=0)
                dp[j] = Math.max(dp[j], dp[j-A[i]]+V[i]);
            }
        }
        return dp[m];
    }
}

所以完全背包问题的时间空间简化版本、和01背包的空间优化版本，其实就只有一个j遍历顺序的差别

518. 零钱兑换 II

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数。

输入：amount = 5, coins = [1, 2, 5]
输出：4
解释：有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

思路：完全背包问题，注意第一行的初始化方式！！

dp[i][j]表示前i索引的硬币，能够拼成j的组合数
dp[i][j] += dp[i][j-coins[i]]
初始化 if(j%coins[0]==0) dp[0][j] = 1,,, dp[i][j]= dp[i-1][j];

代码：

class Solution {
    public int change(int amount, int[] coins) {
        //典型完全背包问题
        //dp[i][j]表示前i索引的硬币，能够拼成j的组合数
        int m = coins.length;
        int[][] dp = new int [m][amount+1];
        //初始化 只要j%coins[0]==0 dp[0][j]=1;
        for(int j=0;j<=amount;j++) if(j%coins[0]==0) dp[0][j] = 1;
        //动态迭代
        for(int i=1;i<m;i++){
            for(int j=0;j<=amount;j++){
                dp[i][j] = dp[i-1][j];
                if(j-coins[i]>=0) dp[i][j] += dp[i][j-coins[i]];
            }
        }
        return dp[m-1][amount];
    }
}

方法二：完全背包，优化空间

dp[j]表示前i索引的硬币，能够拼成j的组合数
dp[j] += [j-coins[i]]
初始化 if(j%coins[0]==0) dp[j] = 1,,, dp[j]= dp[j]

代码：

class Solution {
    public int change(int amount, int[] coins) {
        //典型完全背包问题 优化空间
        //dp[j]表示前i索引的硬币，能够拼成j的组合数
        int m = coins.length;
        int[] dp = new int [amount+1];
        //初始化 只要j%coins[0]==0 dp[0][j]=1;
        for(int j=0;j<=amount;j++) if(j%coins[0]==0) dp[j] = 1;
        //动态迭代
        for(int i=1;i<m;i++){
            for(int j=0;j<=amount;j++){
                //dp[j] = dp[j];
                if(j-coins[i]>=0) dp[j] += dp[j-coins[i]];
            }
        }
        return dp[amount];
    }
}

4 总结

完全背包问题和01背包问题的区别在于是否可以重复选择，对应到代码层面，就是当前行是由当前行推导（完全背包）还是由上一行推导（01背包）

落风的风

背包问题-力扣题解