1. IT分享知识网首页

动态规划—01背包问题详解

老牧童 • • 未分类 • 阅读 85

动态规划—01背包问题详解动态规划01背包问题详解鸣谢：本次的学习是跟着Carl的笔记来的，原创作者为Carl，可以在b站或者公众号关注Carl，搜索代码随想录。一、01背包问题理论基础1、问题​ 有N件物品和一个最多能背重量为W的背包（也就是说背包的容量是W），第i件物品的重量是weight[i]，其价值是val

大家好，欢迎来到IT知识分享网。

动态规划—01背包问题详解

鸣谢：本次的学习是跟着Carl的笔记来的，原创作者为Carl，可以在b站或者公众号关注Carl，搜索代码随想录。

image-20211025141353701

一、01背包问题理论基础

1、问题

​ 有N件物品和一个最多能背重量为W的背包（也就是说背包的容量是W），第i件物品的重量是weight[i]，其价值是value[i]，每件物品只能背一次，求解将哪些物品放到背包里面物品价值的总和最大。

image-20211021100648309

2、二维dp数组下的01背包

①确定dp数组以及下标的含义

dp[i][j]表示：
	当背包容量为j，现有编号为0~i的物品可以拿，此时所能背的价值最大为多少。

image-20211021100752403

②确定递推公式

如何推出dp[i][j]呢？

首先再次明确一下dp[i][j]的含义：

当背包容量为j，现有编号为0~i的物品可以拿，此时所能背的价值最大为多少。

那么就可以分情况来讨论，当前背包容量为j，当前物品的编号为i，那么我们要不要把第i件物品放到背包中。

  • 当前物品编号i不放入背包中，那么dp[i][j] = dp[i-1][j]
  • 当前物品编号i放入背包中，那么dp[i][j] = dp[i-1][j-weight[i]]+value[i]
    • 注意此时的dp[i][j]，意思是当前这个编号的物品放进来了，我们还需要加上value[i]。

综上，我们只需要在这两种情况中，选择最优的，也就是价值最大的dp[i][j]即可。

所以：

dp[i][j] = Math.max( dp[i-1][j] , dp[i-1][j-weight[i]]+value[i] )

③dp数组初始化

大体的思路是根据递推公式来的，从递推公式可以看出，我们需要的是dp[i][j]左上方的数据，所以我们整体循环的方向就是从左到右。从上到下。

我的思路还是通过分情况来讨论：

可能存在两种情况：

  • 当前背包还可以容纳物品，也就是说背包的重量j不为0，但是当前可以拿的物品只有物品编号为0扥物品，也就是说i=0，j≠0的情况。
  • 当前有不同种的物品可以拿，但是背包的重量j为0，也就是说当前背包无法容纳任何的物品，dp[i][j] = 0，这就是i≠0，j=0的情况。

image-20211021102328070

此时已经初始化完了第一行和第一列，那么中间的数该如何初始化呢？

实际编写代码的时候，观察我们的递推公式，我们用的是最大值，所以用-1或者0都可以。如果是比较小的情况，我们就设置为一个大的数。

④确定遍历顺序

我们 有两个维度来描述当前背包和物品的状态，i和j。

那么，是先遍历物品还是先遍历背包的重量呢？

其实两种方法都是可以的。

  • 先遍历物品，然后遍历背包重量。

    • //weight数组的大小 就是物品的个数
for(int i=1;i<weight.length;i++){//遍历物品
    for(int j=0;i<=bagweight;j++){//遍历背包容量
        if(j<weight[i])//如果当前的这个背包容量，比当前这个物品的重量小，那么就自动放弃了。
            dp[i][j] = dp[i-1][j];
        else
            dp[i][j] = Math.max( dp[i-1][j] , dp[i-1][j-weight[i]]+value[i]);
    }
}

  • 先遍历背包，再遍历物品。

    • for(int j=0;j<=bagweight;j++){//遍历背包的容量
    for(int i=1;i<weight.length;i++){//遍历物品
        if(j<weight[i])
            dp[i][j] = dp[i-1][j];
        else
            dp[i][j] = Math.max( dp[i-1][j] , dp[i-1][j-weight[i]]+value[i]);
    }
}

⑤举例推导dp数组

image-20211021103337381

实际在处理的过程当中，我们需要开辟的多大的数组。根据实际情况来决定。

3、一维数组下的01背包

image-20211021104834314

①确定dp数组以及下标的含义

设dp[j]表示，容量为j的背包，所背的物品价值最大为dp[j]。

②确定递推公式

是否把当前的这个物品放入，分两种情况，拿还是不拿。

dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i])

③如何初始化

image-20211021105320971

那么我假设物品价值都是⼤于0的，所以dp数组初始化的时候，都初始为0就可以了。

④一维dp数组的遍历顺序

for(int i = 0; i < weight.size(); i++) { // 遍历物品
 	for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
 		dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
 	}
}

image-20211021105702558

image-20211021105722590

⑤举例推导

image-20211021105858956

二、LeetCode-416.分割等和子集

1、题干

image-20211021110304080

2、动规思路

image-20211021110852475

image-20211021110916937

①确定dp数组以及下标的含义

在01背包中，dp[j]表示：

设dp[j]表示，容量为j的背包，所背的物品价值最大为dp[j]。

套到本题，dp[i]表示 背包总容量是i，最⼤可以凑成i的⼦集总和为dp[i]

②确定递推公式

image-20211021111342676

③初始化

image-20211021111416901

④遍历顺序

image-20211021111546977

⑤举例推导

dp[i]的数值⼀定是⼩于等于i的。
如果dp[i] == i 说明，集合中的⼦集总和正好可以凑成总和i，理解这⼀点很重要

image-20211021111645718

3、一维dp数组代码

class Solution {
    public boolean canPartition(int[] nums) {
		int sum = 0;
        for(int i=0;i<nums.length;i++)
            sum += nums[i];
        if (sum % 2==1) return false;//不能平分俩数组
        sum /= 2;//背包容量
        int[] dp = new int[sum+1];//多一位，因为存在背包容量为0的情况
        
        for(int i=0;i<nums.length;i++){
            for(int j=sum;j>=nums[i];j--){//每一个元素不可重复放入
                dp[j] = Math.max(dp[j],dp[j-nums[i]]+nums[i]);
            }
        }
        
        //集合中的元素正好可以凑成总和sum
        if (dp[sum] == sum) return true;
        return false;
    }
}

我的理解

​ Carl的思路是，先把数组中所有元素总和加起来，然后除以二，这就是每个子集加起来的和，如果不能整除2的话，一定是错误的，从数学的角度上就不能划分成两个相等的子集。

​ 如果从数学的角度上可以划分成两个相等的子集，那么转换为01背包问题，给的nums数组中的每一个元素，就相当于是物品，它的重量也就相当于是它的价值值都是nums[i]。我们背包的容量就是sum/2，并且背包最终能够背的最大价值，肯定不会大于sum/2。

​ 我们要做的任务就是，有sum/2这么大容量的一个背包，有一组物品，存不存在放入其中的几个物品，物品重量使得恰好等于背包容量。01背包最终的结果，是求得了可以放下的最大值，我们最终拿这个最大值和sum/2比较即可。

4、二维dp数组代码

dp[i][j]指的是当前背包容量为j，可以选择的物品为i，所能背的最大价值。

class Solution {
    public boolean canPartition(int[] nums) {
		int sum = 0;
        for(int i=0;i<nums.length;i++)
            sum += nums[i];
        if (sum % 2==1) return false;//不能平分俩数组
        int target = sum/2;//背包的最大容量和最大价值都为target
        
        int[][] dp = new int[nums.length+1][target+1];
        
        for (int i=0;i<nums.length;i++)
            dp[i][0] = 0;
        for (int j=0;j<target+1;j++)
            dp[0][j] = 0;
        
        for (int i=1;i<nums.length+1;i++){
            for (int j=1;j<=target;j++){
                if (nums[i-1] > j) dp[i][j] = dp[i-1][j];//容量放不下当前这个物品的重量
                else
                    dp[i][j] = Math.max( dp[i-1][j] , dp[i-1][j-nums[i-1]]+nums[i-1]);
            }
        }
        
        if (dp[nums.length][target] == target) return true;
        return false;
       
    }
}

最终的数组

测试数据为nums[1,5,11,5]

image-20211021163843816

对比一维的dp数组结果

image-20211021164028543

5、一维dp和二维dp再思考

​ 可以看出一维dp和二维dp的最终状态是一样的，只是一维dp节省了空间复杂度。其次就是一维dp数组，需要倒序的去迭代更新，因为我们取得是Math.max(a,b)，如果我们遍历顺序从前到后，那么后面的值就会被前面的所覆盖。最后，开辟dp数组的大小也很有讲究，开多大，怎么初始化，最终的结果是数组的哪个下标所对应的值？心中要明确好dp[i][j]的含义。

三、LeetCode-1049.最后一块石头的重量II

1、题干

image-20211024150246166

image-20211024150254578

image-20211024150302280

image-20211024151421281

2、动规思路

​ 本题和上面的分割等和子集很像，如何才能使得石头碰撞后重量最小呢？也就是说最好把石头重量分成相近的两堆，相撞之后剩下的石头最小。

​ 本题中物品的重量为store[i]，物品的价值也为store[i]。

​ 对应于01背包中的物品重量weight[i]和价值value[i]。

①确定dp数组以及下标的含义

​ dp[j]表示容量（这⾥说容量更形象，其实就是重量）为j的背包，最多可以背dp[j]这么重的⽯头。

②确定递推公式

01背包的递推公式为：dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
本题则是：dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);

③dp数组初始化

​ dp[j]中的j表示容量，那么j最大为多少呢？答案是所有石头重量的总和

然而我们需要的是target：也就是最大重量（总和）的一半。

④遍历顺序

​ 从左到右，：如果使⽤⼀维dp数组，物 品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒叙遍历。

⑤举例推导

image-20211024151658023

3、一维dp数组代码

class Solution {
    public int lastStoneWeightII(int[] stones) {
		int sum = 0;
        for(int i=0;i<stones.length;i++)
            sum += stones[i];
       	int target = sum/2;//背包容量，尽可能能达到这么大。
        int[] dp = new int[target+1];//多一位，因为存在背包容量为0的情况
        
        for(int i=0;i<stones.length;i++){
            for(int j=target;j>=stones[i];j--){//每一个元素不可重复放入，背包容量够才能放入
                dp[j] = Math.max(dp[j],dp[j-stones[i]]+stones[i]);
            }
        }
        
        return sum - dp[target] - dp[target];
    }
}

思考：

  • 从整体的角度考虑：首先通过计算总和的一半，这样两堆石头撞击会有最小的剩余。
  • 01背包动态规划的特点：有容量为 j 的背包，怎么装物品，最后的价值最大。
  • 如何靠到01背包问题：现在我们的最大容量为target，那么我们怎么装物品，使得总价值（也就是总重量）达到最大。
  • 答案：在最后一个dp[j]我们得到了，容量为 j 的背包，所能装下的最大价值为dp[j]，也就是我们石头堆的最大子总重量。
    • 然后通过总重量，减去2*dp[target]也就是说，最多会有这么多的石头发生碰撞，损失，用总重量减去即可算的剩余的最小重量。

4、二维dp数组代码

dp[i][j]代表指的是当前背包容量为j，可以选择的石头为i，所能背的最大重量。

class Solution {
    public int lastStoneWeightII(int[] stones) {
		int sum = 0;
        for(int i=0;i<stones.length;i++)
            sum += stones[i];
       	int target = sum/2;//背包容量，尽可能能达到这么大。
        int[][] dp = new int[stones.length+1][target+1];//多一位，因为存在背包容量为0的情况
        
        
        for(int i=1;i<stones.length+1;i++){
            for(int j=1;j<target+1;j++){
                if (stones[i-1] > j) 
                    dp[i][j] = dp[i-1][j];//容量放不下当前这个物品的重量
                else
                    dp[i][j] = Math.max( dp[i-1][j] , dp[i-1][j-stones[i-1]]+stones[i-1]);
            }
        }
        
        
        return sum - 2*dp[stones.length][target];
    }
}

四、LeetCode-494.目标和

1、题干

image-20211024161028218

image-20211024161304847

2、动规思路

要想有target，那么分析target从哪里来。

target是最终的结果，target = 左面数字的组合 – 右面数字的组合。即target = left – right

target = left - right
left + right = sum

所以target = left - (sum-left) = 2*left -sum
所以left = (sum + target) / 2（这里要求sum + target）是非负偶数
此时我们就找到了左面组合的值应该为多少。
此时的问题就是在集合中找出和为left的组合共有多少种

①确定dp数组以及下标的含义

dp[i][j]表示在数组nums的前i个数中选取元素，使得这些元素之和等于背包容量j的方案，有dp[i][j]个。

②确定递推公式

分析dp[i][j]的来源
1、如果j<nums[i]，则不能选nums[i]
	此时有dp[i][j] = dp[i-1][j]
2、如果j>=nums[i]，则可以选nums[i]，也可以不选。
	如果选了nums[i]，方案数是dp[i-1][j-nums[i]]
	如果不选nums[i]，方案数是dp[i-1][j]
	所以总的方案数就是：dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i]]

③初始化

如果i=0，那么说明从前0个数中选取元素，元素和肯定为0
	如果j=0，那么dp[i][j]=1
	如果j>=1，那么dp[i][j]=0，即没有方案可以满足j

④遍历顺序

从左到右遍历

⑤最终答案

最终的答案就是dp[nums.length][left]

3、二维dp数组代码

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for(int i=0;i<nums.length;i++)
            sum += nums[i];
        //前提条件
        if((sum + target)%2!=0 || (sum + target)<0 )
            return 0;
        int left = (sum + target)/2;

        int n = nums.length;
        int[][] dp = new int[n+1][left+1];
        //初始化
        dp[0][0] = 1;
        for(int i=1;i<=n;i++){
            int num = nums[i-1];
            for(int j=0;j<=left;j++){
                dp[i][j] = dp[i-1][j];
                if(j >= num)
                    dp[i][j] += dp[i-1][j-num];
            }
        }
        return dp[n][left];
    }
}

五、LeetCode-474.一和零

1、题干

image-20211025140945138

image-20211025141035439

2、动规思路

image-20211025141854702

①确定dp数组下标及其含义

dp[i][j]：最多有i个0和j个1的strs的最大子集的大小为dp[i][j]

②确定递推公式

dp[i][j] 可以由前⼀个strs⾥的字符串推导出来，strs⾥的前一个字符串有zeroNum个0，oneNum个1。
dp[i][j] 就可以是 dp[i - zeroNum][j - oneNum] + 1。（相当于再把当前这个字符串加到子集中去）

然后我们在遍历的过程中，取dp[i][j]的最⼤值。
所以递推公式：dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);

此时⼤家可以回想⼀下01背包的递推公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
对⽐⼀下就会发现，字符串的zeroNum和oneNum相当于物品的重量（weight[i]），字符串本身的个数相当于物品的价值（value[i]）。
这就是⼀个典型的01背包！ 只不过物品的重量有了两个维度⽽已。

③初始化

01背包的dp数组初始化为0就可以，因为物品价值不会是负数，初始为0，保证递推的时候不被覆盖。

④确定遍历顺序

外层for循环遍历物品
	内层for循环遍历背包容量，并且是从后向前遍历

因为我们这里用的相当于是二维的滚动数组，如果从前向后遍历的话，就会发生覆盖与重复。

//通过indexOf()寻找字符串中含有多少个某个字符
public int countString(String str,String s){
    int count = 0,len = str.length();
    while(str.indexOf(s) != -1) {
		str = str.substring(str.indexOf(s) + 1,str.length());
		count++;
	}
    return count;
}
//遍历顺序
for(String str : strs){//外层遍历物品
    int oneNum = 0,zeroNum = 0;
    oneNum = countString(str,"1");
    zeroNum = countString(str,"0");
    
    for(int i=m;i>=zeroNum;i--){//遍历背包容量从后向前
        for(int j=n;j>=onNum;j--){
            dp[i][j] = Math.max(dp[i][j],dp[i-zeroNum][j-oneNum]+1);
        }
    }
}

⑤距离推导dp数组

以输⼊：["10","0001","111001","1","0"]，m = 3，n = 3为例

image-20211025153557031

3、代码

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
		int[][] dp = new int[m+1][n+1];
        //遍历顺序
		for(String str : strs){//外层遍历物品
    		int oneNum = 0,zeroNum = 0;
   			oneNum = countString(str,"1");
    		zeroNum = countString(str,"0");
    
    		for(int i=m;i>=zeroNum;i--){//遍历背包容量从后向前
       			 for(int j=n;j>=oneNum;j--){
            		dp[i][j] = Math.max(dp[i][j],dp[i-zeroNum][j-oneNum]+1);
                }
            }
        }
        return dp[m][n];
    }
    //通过indexOf()寻找字符串中含有多少个某个字符
    public int countString(String str,String s){
        int count = 0,len = str.length();
        while(str.indexOf(s) != -1) {
		    str = str.substring(str.indexOf(s) + 1,str.length());
		    count++;
	    }
    return count;
    }
}

4、再次理解滚动数组（一维dp）和二维dp数组

  • 二维dp数组实际上就是外层循环控制物品，内层循环控制背包，顺序按照具体的题目从前到后或者从后到前。
    • 关键的点是可以物品在外层，也可以背包在外层。
  • 一维dp（滚动数组）就是将物品通过题目给的物品数组来表示了。不需要我们通过特定的dp数组中的属性来表示。

免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://yundeesoft.com/33008.html

赞 (0)
老牧童老牧童
0

相关推荐

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注微信