当前位置:   article > 正文

二维动态规划>>01背包问题与普遍应用_二维背包

二维背包

0、内容梗概

        在二维动态规划中,01背包问题是动态规划中的经典问题。

  •  本文首先学习、总结01背包问题的思路、方法与实现
  •  之后,01背包问题与其说是问题,更可以是一种解题思路,或者说套路

        如果遇到别的题目时,能够清楚地判断出它是一个01背包的类似问题,就可以套用01背包问题的模板,来进行解题。例如416. 分割等和子集 - 力扣(Leetcode)

本文内容即: 
        (1)01背包是什么 
        (2)如何用01背包思想解答其他题目(
416. 分割等和子集 - 力扣(Leetcode)


1、01背包

1.1 介绍01背包问题

      有共n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i],得到的价值是value[i] 每件物品只能用一次,求解将哪些物品装入背包里物品价值总和最大。

物品编号重量价值
物品0115
物品1320
物品2430

        解释:就是在有限的最大重量w,选任意个具有重量和价值的商品(每个商品就1个),求能得到的最大价值。

1.2 解题思路

(1)分析

对于动态规划类型的题目,我们知道:

  1. 需要将大问题拆解为多个小问题来解决
  2. 通过求出所有小问题的答案,放入dp数组,递推到大问题。

        这个题目作为二维动态规划,是因为有2个动态变化的变量:最大背包重量,和,到底从前几?个物品里选。        
       
(至于为什么要这么思考,不需要知道,因为我们要学习01背包的模式,来套其他的题目,因此这就是一个模板)

        因此,可以构建二维dp数组dp[i][j] :
        表示从下标为[0-i]的物品里任意取,放进重量为j的背包,价值总和最大的值。

(2)确定递推公式⭐

        要求二维dp[i][j]的递推公式,其实就是求出dp所有子问题组成全集的方法:
        思路是:先看能不能、再看要不要。

        对于任意 dp[i][j],其意义是最大重量为j的约束下,从0~i这些商品任选,能够得到的最大价值。动态规划的奥秘在于,不要去思考具体是怎么选、怎么组合得到的最大价值,而是仅仅通过“递推”的思想完成整个任务。
        对于dp[i][j]而言,是从0~i里来选的,那么0~i里来选,有可能选了第i个,也有可能没选。
        我们首先要考虑能不能选第i个?
        如果第i个的重量weight[i]比整个背包的最大承重j都要大,那么就算从0~i里选,实际上也肯定不能选第i个。因此,dp[i][j]其实等效于从0~i-1里选,最大容量为j的这个状态。
        即:dp[i][j] = dp[i-1][j]
        其次,我们要考虑:能选,但是要不要选?
       
如果现在能选第i个商品了,即第i个商品有资格被选(重量小于等于总重),就要考虑要不要选:
        如果不要选上第i个,就仍然是等效于从0~i-1里选,最大容量为j。dp[i][j] = dp[i-1][j]
        如果要选上第i个,那么dp[i][j]这个最大价值该等于什么呢?既然选了第i个,至少就有第i个的价值Value[i],然后背包的最大容量只剩下j-weight[i]了,然后从0~i-1里接着选。
        因此,为dp[i - 1][j - weight[i]] + value[i]
        而dp[i][j]为最大价值,因此要取两种情况的Max。
        dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

(3)初始化数组
 

        初始化数组要考虑数组的意义。
        首先,在j为0这一列,最大重量都为0了,你怎么组合也甭想装进去啊。因此dp[i][0]全为0
        其次,i为0这一行 ,相当于从0~0的物品里任选(其实就是只选物品0),背包重量为j的约束下,能取得的最大价值。因为物品就1个,只能用一次,因此,在j>=weight[i]的列,都应该为Value[i].

(4)代码实现     

  1. package LeetcodeLearn.Algorithm.sort;
  2. import java.util.Arrays;
  3. /**
  4. * @Author ZhangQihao
  5. */
  6. public class package0_1 {
  7. public static void main(String[] args) {
  8. int[] weight = {1,3,4};
  9. int[] value = {15,20,30};
  10. int bagSize = 4;
  11. testWeightBagProblem(weight,value,bagSize);
  12. }
  13. /**
  14. * 动态规划获得结果
  15. * @param weight 物品的重量
  16. * @param value 物品的价值
  17. * @param bagSize 背包的容量
  18. */
  19. public static void testWeightBagProblem(int[] weight, int[] value, int bagSize){
  20. // 创建dp数组
  21. int goods = weight.length; // 获取物品的数量
  22. int[][] dp = new int[goods][bagSize + 1];
  23. // 初始化dp数组
  24. // 创建数组后,其中默认的值就是0
  25. for (int j = weight[0]; j <= bagSize; j++) {
  26. dp[0][j] = value[0];
  27. }
  28. // 填充dp数组:i是物品标号
  29. // j是:容量为j的背包
  30. for (int i = 1; i < weight.length; i++) {
  31. for (int j = 1; j <= bagSize; j++) {
  32. //能不能?
  33. if (j < weight[i]) {
  34. dp[i][j] = dp[i-1][j];
  35. } else {
  36. //能,但是要不要?
  37. dp[i][j] = Math.max(dp[i-1][j] , dp[i-1][j-weight[i]] + value[i]);
  38. //前为不要,后为要。
  39. }
  40. }
  41. }
  42. // 打印dp数组
  43. for (int i = 0; i < goods; i++) {
  44. for (int j = 0; j <= bagSize; j++) {
  45. System.out.print(dp[i][j] + "\t");
  46. }
  47. System.out.println("\n");
  48. }
  49. }
  50. }

2、01背包问题的模板套用 

2.1 如何套用01背包模板

        如何把01背包问题套用到其他问题上,以416. 分割等和子集 - 力扣(Leetcode)为例子进行说明。

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

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

        能否分成两个等和数组,其实可以变换为:选任意多个数字的和,为所有数字总和 / 2。
        如果像下面这样考虑,这个问题就类似01背包问题了。

        相当于:坐标是商品标号,数值是商品的重量,要往一个背包里装,背包的最大重量为所有数值和/2。
        即:从下标0~i选取其中任意的数字,是否存在一种方案,使其和为j
        即:推出每一个状态,直到i为数组末位,j为和的二分之一,输出dp。

         到这里就很清晰了,其余分析类似上文,也可看代码注释。

2.2 代码实现及解释

  1. class Solution {
  2. public boolean canPartition(int[] nums) {
  3. //从下标0~i选取其中任意的数字,是否存在一种方案,使其和为j
  4. //如果能够构建这个问题的状态方程,那么推导到i=nums.length-1、j=数组和/2的时候
  5. //dp数组的值就是最终的答案了。
  6. int n = nums.length;
  7. //长度为1,不可分
  8. if(n == 1){
  9. return false;
  10. }
  11. //和为奇数,不可平分
  12. int sum = 0,MaxNum = 0;
  13. for(int num : nums){
  14. sum += num;
  15. MaxNum = Math.max(MaxNum,num);
  16. }
  17. if(sum % 2 == 1){
  18. return false;
  19. }
  20. //如果数组中的最大值,大于了和的1/2,不可平分
  21. int target = sum / 2;
  22. if(MaxNum > target){
  23. return false;
  24. }
  25. //构建动态dp
  26. boolean[][] dp = new boolean[n][target + 1];//画图即可
  27. //初始化:
  28. for(int i = 0; i < n; i++){
  29. dp[i][0] = true;//从0~i索引,选取一种方案能否组成和为0的集合:当然可以,一个数字也不选,这种方案可行
  30. }
  31. dp[0][nums[0]] = true;
  32. for(int i = 1; i < n; i++){
  33. for(int j = 1; j < target + 1; j++){
  34. //先判断能不能选
  35. if(nums[i] > j){
  36. //不能选
  37. dp[i][j] = dp[i - 1][j];
  38. }else{
  39. //能选,需要考虑要不要选
  40. dp[i][j] = dp[i - 1][j] | dp[i - 1][j - nums[i]];
  41. }
  42. }
  43. }
  44. return dp[n - 1][target];
  45. }
  46. }

3、总结

        还有非01状态的背包问题等相关多维动态规划问题,以后熟练了再继续写。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/花生_TL007/article/detail/466266
推荐阅读
相关标签
  

闽ICP备14008679号