精华内容
下载资源
问答
  • 在01背包问题中,在选择是否要把一个物品加到背包中,必须把该物品加进去的子问题的解与不取该物品的子问题的解进行比较,这种方式形成的问题导致了许多重叠子问题,使用动态规划来解决。n=5是物品数量,c=10是...
  • 动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从子问题解得到原问题解。 但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用...

    一、动态规划算法概述

    动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从子问题解得到原问题解。

    在这里插入图片描述

    但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解极值问题时,有些子问题被重复计算了许多次。

    在这里插入图片描述

    如果能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,就可以避免大量重复计算,从而得到多项式时间算法。

    在这里插入图片描述

    动态规划 VS 分治法

    • 相同点:基本思想均是将原问题分解成若干个子问题,先求子问题,然后从子问题的解得到原问题的解;
    • 不同点:
      • 适用于动态规划求解的问题,分解得到的子问题往往不是互相独立的;
      • 动态规划为自底向上,而分治法为自顶向下。

    当分解出的子问题不相互独立的话,若使用分治法来求解此类问题,会导致使用指数级的运行时间,而子问题的个数只有多项式量级。所以,此类问题不适合使用分治法。

    动态规划是如何减少对重复子问题求解的呢?

    答案是保存已求解的子问题的解,在需要时找出,从而避免大量的重复计算得到多项式的运行时间;通常用一个表来记录所有已解决的子问题。

    动态规划算法通常用于求解具有某种最优性质的问题

    二、背包问题

    2.1 什么是背包问题

    今年的年会,聪明大方的老板为了激励员工,决定买三种类型的奖品奖励给勤奋的员工小王。

    在这里插入图片描述

    为了让自己不至于放血太多又不会显得太抠门,美其名曰考验员工小王的智商。机智的老板想到了一个好法子:给小王发一个最大能装下 4 磅物品的背包,只有装到背包中的物品才归属于小王。

    如果你是员工小王,怎么装才能得到最大的物品价值呢?

    2.2 背包问题思路分析

    首先,最容易想到的方法,就是计算出各种可能的奖品组合的情况,找出价值最高的组合放入到背包中。对于三种奖品,共有 8 种的组合,对于四种奖品,共有 16 种组合。每增加一种奖品,需要计算的组合数都将翻倍。如果明年老板决定奖励十一种奖品给小王,那小王最好还是放弃奖品算了。我们可以看到,这种算法的时间复杂度为 O(2ⁿ),效率较低。

    如何找到最优解呢?答案是使用动态规划

    对于背包问题,可以先解决小背包(子背包)的问题,然后逐步解决原来的问题。

    在这里插入图片描述

    每个动态规划算法都从一个网格开始,背包问题的网格如下。

    在这里插入图片描述

    网格的各行为奖品,各列为不同容量(1~4磅)的背包。所有这些列都是必要的,因为它们将用于计算子背包中的物品价值。

    第一步:

    我们首先假设可选择的奖品只有吉他(1 磅)。当背包的容量为 1 时,刚好放下一个吉他,此时背包价值为 1500。当背包的容量为 2、3、4 时,由于可选的商品只有吉他且同样的奖品只能拿一件,因此即便会使背包的空间浪费,背包中仍然是只能放一个吉他,背包中的价值仍然为 1500。

    在这里插入图片描述

    第二步:

    我们再假设可选的商品只有吉他(1 磅)和音响(4 磅)。当背包的容量为 1、2、3 时,由于音响的重量为 4,因此无法放入到背包中,背包中只能放入一个吉他。

    在这里插入图片描述

    当背包的容量为 4 时,刚好等于音响的重量。这个时候有两个选择:一是只放入一个吉他;二是只放入一个音响。由于音响的价值为 3000,大于吉他的价值,因此选择将音响放入背包,此时背包中的价值为 3000。

    在这里插入图片描述

    第三步:

    我们在假设可选择商品有吉他(1 磅)、音响(4 磅)、笔记本电脑(3 磅)。当背包的容量为 1、2 时,毫无疑问,背包中只能放一个吉他。此时背包的价值为 1500。

    在这里插入图片描述

    当背包的容量为 3 时,有两种选择:一是只放入一个吉他;二是只放入一个电脑。由于电脑的价值高于吉他,因此将电脑放入。此时背包的价值为 2000。

    在这里插入图片描述

    当背包的容量为 4 时,仍然有两种选择:一是放入一个吉他和电脑;二是只放入一个音响。由于吉他和电脑的总价值高于音响的价值,因此将吉他和电脑放入。此时背包的价值为 1500 + 2000 = 3500。

    在这里插入图片描述

    因此,将吉他和笔记本电脑装入背包时价值最高,这就是小王的最优解。

    总结:

    那么这个过程,如何用数学公式表达呢?

    我们首先约定一共有 N 件物品,第 i 件物品的重量为 w[i],价值为 v[i],背包的承载上限为 W。再约定一个状态 cell[i][j] 表示将前 i 件(这里的前 i 件指的是有 i 件可选)物品装进限重为 j 的背包可以获得的最大价值(0<=i<=N0<=j<=W)。

    那么我们可以将 cell[0][0...W] 初始化为 0,表示将前 0 个物品装入书包的最大价值为 0。

    i>0 时,cell[i][j] 有两种情况:

    1. 不装入第 i 件物品,则背包最大价值就是相同背包容量下只有 i-1 件物品可选时的最大价值,即 cell[i-1][j]
    2. 装入第 i 件物品(若背包容量够),则最大价值为当前物品价值加背包剩余容量的最大价值,即 v[i] + cell[i-1][j-w[i]]

    那么 cell[i][j] 的值,就是这两种情况下的最大值。由此可以得到方程:
    c e l l [ i ] [ j ] = m a x { c e l l [ i − 1 ] [ j ] c e l l [ i − 1 ] [ j − w [ i ] ] + v [ i ] j > = w [ i ] cell[i][j] = max \left \{\begin {aligned}&cell[i-1][j]\\&cell[i-1][j-w[i]] + v[i]\end{aligned}\right. \quad\quad j>=w[i] cell[i][j]=max{cell[i1][j]cell[i1][jw[i]]+v[i]j>=w[i]
    求得所有的 cell[i][j] 之后,最后一个值就是背包问题的最大值。

    2.3 背包问题代码实现

    public static void main(String[] args) {
        int[] w = {0, 1, 4, 3};    // 物品的重量
        int[] v = {0, 1500, 3000, 2000};    // 物品的价值
    
        int num = w.length; // 物品的数量可能的个数 (0~3,共 3 个)
        int weight = 5; // 背包的容量可能的个数 (0~4,共 5 个)
    
        int[][] cell = new int[num][weight];    // cell[i][j] 表示前i个物品可选,背包容量为j时的最大价值
        int[][] record = new int[num][weight];  // record[i][j] 用于标记第i个物品有没有放入容量为j的背包
    
        for (int i=1; i<num; i++){  // 遍历物品
            for (int j=1; j<weight; j++){   // 遍历背包容量
                if (w[i]>j){    // 如果当前物品重量大于背包容量
                    cell[i][j] = cell[i-1][j];  // 不装入
                }else{  // 如果当前物品重量小于等于背包容量
                    int value_1 = cell[i-1][j]; // 不放入第 i 个物品的背包价值
                    int value_2 = v[i] + cell[i-1][j-w[i]]; // 放入第 i 个物品后的价值
                    /* 把最大价值放入背包 */
                    if (value_1 > value_2){
                        cell[i][j] = value_1;
                    }else{
                        cell[i][j] = value_2;
                        record[i][j] = 1;   // 用于标记在本网格放入了第 i 个物品
                    }
                }
            }
        }
    
        // 最后一个网格就是最大价值
        System.out.println("背包价值为:" + cell[num-1][weight-1]);
    
        // 由于最后一个网格就是最大价值
        // 因此,逆序遍历 record 找到最后一个放入的物品,然后找到剩余空间价值是放入第几个物品
        int i = record.length-1;
        int j = record[0].length-1;
        while (i > 0 && j > 0){
            if (record[i][j] == 1){
                System.out.printf("放入了第 %d 个商品\n", i);
                j = j - w[i];   // 背包剩余容量
            }
            i--;
        }
    }
    

    运行结果如下:

    在这里插入图片描述
    【注】:本文的图大多出自《算法图解》。

    展开全文
  • 思路:定义一个二维数组,一维为物品数量(表示每个物品),二维是重量(不超过最大,这里是15),下面数组a, 动态规划原理思想,max(opt(i-1,w),wi+opt(i-1,w-wi)) 当中最大值, opt(i-1,w-wi)指上一个最优解 <?php ...
  • 动态规划背包问题——01背包

    千次阅读 2021-11-24 15:56:06
    文章目录一、01背包问题二、二维dp数组解决01背包问题1. 确定dp数组以及下标的含义2. 确定递推公式3. dp数组初始化4. 确定遍历顺序5. 举例推导dp数组三、一维dp数组解决01背包问题1. 确定dp数组以及下标的含义2. 一...


    背包问题中我们常见的就是 01背包完全背包。在leetcode的题库中主要就是这两种类型的题目。而完全背包又是也是01背包稍作变化而来,即:完全背包的物品数量是无限的。所以背包问题的基础就是01背包问题。完全背包问题请参考 动态规划之背包问题——完全背包

    在这里插入图片描述

    一、01背包问题

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

    每一件物品其实只有两个状态,取或者不取,所以可以使用回溯法搜索出所有的情况,那么时间复杂度就是O(2^n)。

    所以需要动态规划来解题。

    二、二维dp数组解决01背包问题

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

    dp[i][j] 表示从下标为[0-i]的物品里任意取,放进容量为j的背包,价值总和最大是多少

    在这里插入图片描述

    2. 确定递推公式

    从两个方向推出来dp[i][j]

    1. 不放物品i:由dp[i - 1][j]推出,即背包容量为j,里面不放物品i的最大价值,此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量时,物品i无法放进背包中,所以被背包内的价值依然和前面相同。)
    2. 放物品i:由dp[i - 1][j - weight[i]]推出,dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值,那么dp[i - 1][j - weight[i]] + value[i] (物品i的价值),就是背包放物品i得到的最大价值

    递推公式:dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

    3. dp数组初始化

    首先从dp[i][j]的定义出发,如果背包容量j为0的话,即dp[i][0],无论是选取哪些物品,背包价值总和一定为0。

    状态转移方程 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 可以看出i 是由 i-1 推导出来,那么i为0的时候就一定要初始化。

    dp[0][j],即:i为0,存放编号0的物品的时候,各个容量的背包所能存放的最大价值。

    j < weight[0]的时候,dp[0][j] 应该是 0,因为背包容量比编号0的物品重量还小。

    j >= weight[0]时,dp[0][j] 应该是value[0],因为背包容量放足够放编号0物品。

    for (int j = 0 ; j < weight[0]; j++) {  // 当然这一步,如果把dp数组预先初始化为0了,这一步就可以省略。
        dp[0][j] = 0;
    }
    // 正序遍历
    for (int j = weight[0]; j <= bagWeight; j++) {
        dp[0][j] = value[0];
    }
    

    一开始把数组统一初始化为0,更方便。

    4. 确定遍历顺序

    有两个遍历维度:物品和背包重量。 所以要确定遍历顺序。

    两者都可以,先遍历物品好理解。

    先遍历物品,然后遍历背包重量:

    // weight数组的大小 就是物品个数
    for(int i = 1; i < weight.size(); i++) { // 遍历物品
        for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量
            if (j < weight[i]) dp[i][j] = dp[i - 1][j]; 
            else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
    
        }
    }
    

    先遍历背包,再遍历物品:

    // weight数组的大小 就是物品个数
    for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量
        for(int i = 1; i < weight.size(); i++) { // 遍历物品
            if (j < weight[i]) dp[i][j] = dp[i - 1][j];
            else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
        }
    }
    

    为什么两种顺序都可以?要理解递归的本质和递推的方向

    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 递归公式中可以看出dp[i][j]是靠dp[i-1][j]和dp[i - 1][j - weight[i]]推导出来的。

    dp[i-1][j]dp[i - 1][j - weight[i]] 都在dp[i][j]的左上角方向(包括正上方向),

    那么先遍历物品,再遍历背包的过程和先遍历背包,再遍历物品,dp[i][j]所需要的数据就是左上角,根本不影响dp[i][j]公式的推导。

    5. 举例推导dp数组

    在这里插入图片描述在这里插入图片描述最终结果就是dp[2][4]。

    完整Java测试代码:

    public static void testWeightBagProblem(int[] weight, int[] value, int bagSize){
            //定义dp数组:dp[i][j]表示背包容量为j时,前i个物品能获得的最大价值
            int[][] dp = new int[wLen + 1][bagSize + 1];
            //初始化:背包容量为0时,能获得的价值都为0
            for (int j = weight[0]; j <= bagWeight; j++) {
                dp[0][j] = value[0];
            }
            //遍历顺序:先遍历物品,再遍历背包容量
            for (int i = 1; i <= weight.length; i++){
                for (int j = 1; j <= bagSize; j++){
                    if (j < weight[i - 1]){
                        dp[i][j] = dp[i - 1][j];
                    }else{
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + value[i - 1]);
                    }
                }
            }
        }
    

    三、一维dp数组解决01背包问题

    把二维dp降为一维dp,即使用一维滚动数组。

    在使用二维数组的时候,递推公式:dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

    滚动数组的由来,需要满足的条件是上一层可以重复利用,直接拷贝到当前层。

    dp[i][j] 表示从下标为[0-i]的物品里任意取,放进容量为j的背包,价值总和最大是多少。

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

    在一维dp数组中,dp[j]表示:容量为j的背包,所背的物品价值可以最大为dp[j]

    2. 一维dp数组的递推公式

    dp[j]可以通过dp[j - weight[i]]推导出来,dp[j - weight[i]]表示容量为j - weight[i]的背包所背的最大价值。

    dp[j - weight[i]] + value[i] 表示 容量为 j - 物品i重量 的背包加上物品i的价值。(也就是容量为j的背包,放入物品i了之后的价值即:dp[j]

    dp[j]有两个选择,一个是取自己dp[j] 相当于二维dp数组中的dp[i-1][j],即不放物品i,一个是取dp[j - weight[i]] + value[i],即放物品i,指定是取最大的。

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

    3. 一维dp数组如何初始化

    dp[j]表示:容量为j的背包,所背的物品价值可以最大为dp[j],那么dp[0]就应该是0,因为背包容量为0所背的物品的最大价值就是0。

    假设物品价值都是大于0的,所以dp数组初始化的时候,都初始为0就可以了。

    4. 一维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]);
        }
    }
    

    和二维dp的写法中,遍历背包的顺序是不一样的!

    一维dp遍历的时候,背包是从大到小:倒叙遍历是为了保证物品i只被放入一次!

    一旦正序遍历,那么物品0就会被重复加入多次。

    举一个例子:物品0的重量weight[0] = 1,价值value[0] = 15

    如果正序遍历

    dp[1] = dp[1 - weight[0]] + value[0] = 15

    dp[2] = dp[2 - weight[0]] + value[0] = 30

    此时dp[2]就已经是30了,意味着物品0,被放入了两次,所以不能正序遍历。

    倒叙就是先算dp[2]

    dp[2] = dp[2 - weight[0]] + value[0] = 15 (dp数组已经都初始化为0)

    dp[1] = dp[1 - weight[0]] + value[0] = 15

    所以从后往前循环,每次取得状态不会和之前取得状态重合,这样每种物品就只取一次了。

    但对于二维dp,dp[i][j]都是通过上一层即dp[i - 1][j]计算而来,本层的dp[i][j]并不会被覆盖!

    两个嵌套for循环的顺序先遍历物品嵌套遍历背包容量

    因为一维dp的写法,背包容量一定是要倒序遍历,如果遍历背包容量放在上一层,那么每个dp[j]就只会放入一个物品,即:背包里只放入了一个物品。

    5. 举例推导dp数组

    一维dp,分别用物品0,物品1,物品2 来遍历背包,最终得到结果如下:
    在这里插入图片描述
    完整Java测试代码

    public static void testWeightBagProblem(int[] weight, int[] value, int bagWeight){
            //定义dp数组:dp[j]表示背包容量为j时,能获得的最大价值
            int[] dp = new int[bagWeight + 1];
            //遍历顺序:先遍历物品,再遍历背包容量
            for (int i = 0; i < weight.length; i++){
                for (int j = bagWeight; j >= weight[i]; j--){
                    dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
                }
            }
        }
    

    可以看出,一维dp 的01背包,要比二维简洁的多!而且空间复杂度还降了一个数量级!

    四、leetcode例题讲解01背包问题

    416. 分割等和子集

    leetcode题目链接:416. 分割等和子集

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

    示例一:

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

    示例二:

    输入:nums = [1,2,3,5]
    输出:false
    解释:数组不能分割成两个元素和相等的子集。
    

    这道题目是要找是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。

    那么只要找到集合里能够出现 sum / 2 的子集总和,就算是可以分割成两个相同元素和子集了。

    本题中我们要使用的是01背包,因为元素我们只能用一次

    首先,本题要求集合里能否出现总和为 sum / 2 的子集。那么来一一对应一下本题,看看背包问题如果来解决。

    1. 背包的体积为sum / 2
    2. 背包要放入的商品(集合里的元素)重量为 元素的数值,价值也为元素的数值
    3. 背包如何正好装满,说明找到了总和为 sum / 2 的子集。
    4. 背包中每一个元素是不可重复放入。

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

    套到本题,dp[i]表示 背包总容量是i,最大可以凑成i的子集总和为dp[i]。

    2.确定递推公式

    本题,相当于背包里放入数值,那么物品i的重量是nums[i],其价值也是nums[i]。

    所以递推公式:dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);

    3.dp数组如何初始化

    题目中 只包含正整数的非空数组,所以非0下标的元素初始化为0就可以了。

    4.确定遍历顺序

    for(int i = 0; i < nums.size(); i++) {
        for(int j = target; j >= nums[i]; j--) { // 每一个元素一定是不可重复放入,所以从大到小遍历
            dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
        }
    }
    

    5.举例推导dp数组
    dp[i]的数值一定是小于等于i的。

    如果dp[i] == i 说明,集合中的子集总和正好可以凑成总和i,理解这一点很重要。

    用例1,输入[1,5,11,5] 为例,如图:
    在这里插入图片描述
    最后dp[11] == 11,说明可以将这个数组分割成两个子集,使得两个子集的元素和相等。

    完整Java代码:

    class Solution {
        public boolean canPartition(int[] nums) {
            if(nums == null || nums.length == 0) return false;
            int n = nums.length;
            int sum = 0;
            for(int num : nums){
                sum += num;
            }
            //总和为奇数,不能平分
            if(sum % 2 != 0) return false;
            int target = sum / 2;
            int[] dp = new int[target + 1];
            for(int i = 0; i < n; i++){
                for(int j = target; j >= nums[i]; j--){
                    //物品 i 的重量是 nums[i],其价值也是 nums[i]
                    dp[j] = Math.max(dp[j], dp[j-nums[i]] + nums[i]);
                }
            }
            return dp[target] == target;
        }
    }
    
    

    这道题目就是一道01背包应用类的题目,需要我们拆解题目,然后套入01背包的场景。

    01背包相对于本题,主要要理解,题目中物品是nums[i],重量是nums[i],价值也是nums[i],背包体积是sum/2。

    1049. 最后一块石头的重量 II

    leetcode题目链接:1049. 最后一块石头的重量 II

    有一堆石头,用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。

    每一回合,从中选出任意两块石头,然后将它们一起粉碎。假设石头的重量分别为 x 和 y,且 x <= y。那么粉碎的可能结果如下:

    如果 x == y,那么两块石头都会被完全粉碎;
    如果 x != y,那么重量为 x 的石头将会完全粉碎,而重量为 y 的石头新重量为 y-x。
    

    最后,最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下,就返回 0。

    示例一:

    输入:stones = [2,7,4,1,8,1]
    输出:1
    解释:
    组合 24,得到 2,所以数组转化为 [2,7,1,8,1],
    组合 78,得到 1,所以数组转化为 [2,1,1,1],
    组合 21,得到 1,所以数组转化为 [1,1,1],
    组合 11,得到 0,所以数组转化为 [1],这就是最优值。
    

    示例二:

    输入:stones = [31,26,33,21,40]
    输出:5
    

    本题其实就是尽量让石头分成重量相同的两堆,相撞之后剩下的石头最小,这就回到了上一题分割等和子集,就化解成01背包问题了。

    背包体积为sum/2,物品的重量stones[i],物品的价值stones[i]。

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

    dp[i] 表示容量为i的背包最多可以装dp[i]重的石头

    2.确定递推公式

    dp[j] = max(dp[j], dp[j-stones[i]]+stones[i])
    

    3.dp数组如何初始化

    同上。

    4.确定遍历顺序

    同上,先遍历物品,然后倒序遍历背包。

    完整Java代码:

    class Solution {
        public int lastStoneWeightII(int[] stones) {
            int sum = 0;
            for(int stone : stones){
                sum += stone;
            }
            int target = sum / 2;
            int[] dp = new int[target+1];
            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 - 2 * dp[target];
        }
    }
    

    494. 目标和

    leetcode题目链接: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
    

    示例二:

    输入:nums = [1], target = 1
    输出:1
    

    本题其实是让数组中的数字分成添加正号的数字和与添加负号的数字和相等,就化解成01背包的组合问题。

    计算相等的方法有几种,就是组合问题。

    这里可以设添加负号的数字和为neg (也可以设正号的),总和为sum,则添加正号的数字和为sum - neg。

    要求 (sum - neg ) - neg= target,则neg = (sum - target) / 2。

    判断target的值和sum的值的大小,如果target大,没有方案,不能整除也没有方案,都是非负整数。

    转化为背包体积为neg= (sum - target) / 2,重量和价值都为nums[i]

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

    dp[j] 表示元素和为j时的表达式数目

    2.确定递推公式

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

    求组合类问题的公式,都是类似这种。

    3.dp数组如何初始化

    从递归公式可以看出,在初始化的时候dp[0] 一定要初始化为1,因为dp[0]是在公式中一切递推结果的起源,如果dp[0]是0的话,递归结果将都是0。

    dp[0] = 1,理论上也很好解释,装满容量为0的背包,有1种方法,就是装0件物品。

    4.确定遍历顺序

    同上,先遍历物品,然后倒序遍历背包。

    完整Java代码:

    class Solution {
        public int findTargetSumWays(int[] nums, int target) {
            // 动态规划,一个正集,一个负集,和为target
            // 设元素和为sum,负号和为neg,正号和为sum-neg ,则(sum-neg)-neg = target, neg = (sum - target) / 2
            // 装满背包体积为neg,重量和价值为nums[i]的方法有几种
            // dp[j] 表示元素和为j时的表达式数目
            int sum = 0;
            for(int num : nums){
                sum += num;
            }
            int diff = sum - target; // 判断target的值和sum的值的大小,如果target大,没有方案,不能整除也没有方案,都是非负整数
            if(diff < 0 || diff % 2 != 0) return 0; 
            int neg = diff / 2; // 添加负号集的和
            int[] dp = new int[neg+1];
            dp[0] = 1;
            for(int i = 0; i < nums.length; i++){
                for(int j = neg; j >= nums[i]; j--){
                    dp[j] += dp[j - nums[i]];  // 组合问题
                }
            }
            return dp[neg];
        }
    }
    

    474. 一和零

    leetcode题目链接:474. 一和零

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

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

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

    示例一:

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

    示例二:

    输入:strs = ["10", "0", "1"], m = 1, n = 1
    输出:2
    解释:最大的子集是 {"0", "1"} ,所以答案是 2

    这道题可以说是一个变形的01背包问题,本题中strs 数组里的元素就是物品,每个物品都是一个!

    而m 和 n相当于是一个背包,两个维度的背包。而不同长度的字符串就是不同大小的待装物品。

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

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

    2.确定递推公式

    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);
    

    对比一下就会发现,字符串的zeroNum和oneNum相当于物品的重量(weight[i]),字符串本身的个数相当于物品的价值(value[i])。

    这就是一个典型的01背包! 只不过物品的重量有了两个维度而已。

    3.dp数组如何初始化

    因为物品价值不会是负数,初始为0,保证递推的时候dp[i][j]不会被初始值覆盖。

    4.确定遍历顺序

    物品就是strs里的字符串,背包容量就是题目描述中的m和n。

    所以背包倒序遍历的时候需要遍历两个维度。

    完整Java代码:

    class Solution {
        public int findMaxForm(String[] strs, int m, int n) {
            // 动态规划,01背包问题,背包有两个维度,一个m,一个n.
            // strs 数组里的元素就是物品,每个物品都是一个,不同长度的字符串都是待装物品
            // dp[i][j]表示最多有i个0,j个1的strs的最大子集长度
            // dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
            int zeroNum, oneNum;
            int[][] dp = new int[m+1][n+1];
            for(String str : strs){  // 先统计每个字符串0的个数和1的个数,遍历物品
                zeroNum = 0;
                oneNum = 0;
                for(char c : str.toCharArray()){
                    if(c == '0') zeroNum++;
                    else oneNum++;
                }
                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];
        }
    }
    

    五、01背包问题总结

    1. 动规五步分析法

    1. 确定dp数组(dp table)以及下标的含义
    2. 确定递推公式
    3. dp数组如何初始化
    4. 确定遍历顺序
    5. 举例推导dp数组

    2. 背包递推公式

    问能否能装满背包(或者最多装多少):dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]); ,对应题目如下:

    416. 分割等和子集

    1049. 最后一块石头的重量 II

    问装满背包有几种方法:dp[j] += dp[j - nums[i]] ,对应题目如下:

    494. 目标和

    问背包装满最大价值(多维背包问题):dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); ,对应题目如下:

    474. 一和零

    3. 遍历顺序

    二维dp数组01背包先遍历物品还是先遍历背包都是可以的,且第二层for循环是从小到大遍历

    一维dp数组01背包只能先遍历物品再遍历背包容量,且第二层for循环是从大到小遍历

    动态规划其它题型总结:

    动态规划之背包问题——完全背包

    动态规划之打家劫舍系列问题

    动态规划之股票买卖系列问题

    动态规划之子序列问题

    参考:代码随想录:背包理论基础01背包

    展开全文
  • 此类问题应该用动态规划的方式进行求解,将背包的容量进行一个分解;分解为1-5;然后将1-3号商品逐一添加到容量不同的背包中去。图解如下1.png该算法的核心思想就是当容量足够可以放入一个物品的时候你要将这个值与...

    问题 当前有一个容量为5的背包 有三种商品价值和质量分别为 :

    1 v = 6;w=1;

    2 v=10;w=2;

    3 v=12 ;w=3;

    求解不超过背包容量的情况下获取最大值的商品。

    此类问题应该用动态规划的方式进行求解,将背包的容量进行一个分解;分解为1-5;然后将1-3号商品逐一添加到容量不同的背包中去。图解如下

    0b3a64d89a64

    1.png

    该算法的核心思想就是当容量足够可以放入一个物品的时候你要将这个值与你之前的最优解进行一个比较

    就是 当前物品的价值+背包减去此物品w后的最优解 与 不放这个物品时的最优解进行比较。

    代码如下

    public static void main(String[] args) {

    int r = 5;

    int[] v= {6,10,12};//物品的质量

    int[] w = {1,2,3};//物品的重量

    //构造这个二维数组,其实这个二维数组就是之前图中所画的那个数组

    int[][]dp = new int[4][6];

    int n = v.length;//物品的数量

    for(int i= 0;i

    for(int j = 0;j

    dp[i][j]=0;

    }

    }

    //循环物品的数量

    for(int i = 1;i<=n;i++){

    //循环背包的容量

    for(int j = 1;j<=r;j++){

    if(w[i-1]<=j){

    dp[i][j]=Math.max((v[i-1]+dp[i-1][j-w[i-1]]), dp[i-1][j]);

    }else{

    dp[i][j]=dp[i-1][j];

    }

    }

    }

    for(int i= 0;i

    for(int j = 0;j

    System.out.print(dp[i][j]+" ");

    }

    System.out.println();

    }

    }

    展开全文
  • 《算法图解》-9动态规划 背包问题,行程最优化

    千次阅读 多人点赞 2019-06-11 23:10:40
    背包问题,在可装物品有限的前提下,尽量装价值最大的物品,如果物品数量足够大,简单的暴力穷举法是不可行的O(2ⁿ),前一章介绍了《贪婪算法》就是解决如何找到近似解,这接近最优解,但可能不是最优解。...

    本文属于《算法图解》系列。学习动态规划,这是一种解决棘手问题的方法,它将问题分成小问题,并先着手解决这些小问题。

    一 背包问题

        背包问题,在可装物品有限的前提下,尽量装价值最大的物品,如果物品数量足够大,简单的暴力穷举法是不可行的O(2ⁿ), 前一章介绍了《贪婪算法》就是解决如何找到近似解,这接近最优解,但可能不是最优解。如何找到最优解呢?就是动态规划算法。动态规划先解决子问题,再逐步解决大问题。

      每个动态规划算法都从一个网格开始,背包问题的网格如下。

      网格的各行为商品,各列为不同容量(1~4磅)的背包。所有这些列你都需要,因为它们将帮助你计算子背包的价值。网格最初是空的。你将填充其中的每个单元格,网格填满后,就找到了问题的答案。

    1 吉他行

      这是第一行,只有吉他可供你选择。第一个单元格表示背包的容量为1磅。吉他的重量也是1磅,这意味着它能装入背包!因此这个单元格包含吉他,价值为1500美元。来看下一个单元格。这个单元格表示背包的容量为2磅,完全能够装下吉他!以此类推。

    你知道这不是最终的解。随着算法往下执行,你将逐步修改最大价值。

    2 音响行

    可选的有吉他和音响。在每一行, 可选的商品都为当前行的商品以及之前各行的商品。

    背包的容量为1磅,能装下音响吗?音响太重了,装不下!由于容量1磅的背包装不下音响, 因此最大价值依然是1500美元。接下来的两个单元格的情况与此相同,背包容量为4磅呢?终于能够装下音响了!

    3 笔记本电脑行

    下面以同样的方式处理笔记本电脑。笔记本电脑重3磅,没法将其装入容量为1磅或2磅的背 包,因此前两个单元格的最大价值还是1500美元。对于容量为3磅的背包,可选笔记本电脑而不是吉他,这样新的最大价值将为2000美元!

      

    对于容量为4磅的背包,情况很有趣。这是非常重要的部分。当前的最大价值为3000美元,选择笔记本电脑2000美元,还有1磅空间没用使用。根据之前计算的最大价值可知,在1磅的容量中可装入吉他,价值1500美元。因此,你需要做如下比较。

    为何计算小背包可装入的商品的最大价值呢?因为余下了空间时,你可根据这些子问题的答案来确定余下的空间可装入哪些商品。笔记本电脑和吉他的总价值为3500美元,最终的网格类似于下面这样。

       你可能认为,计算最后一个单元格的价值时,我使用了不同的公式。那是因为填充之前的单元格时,我故意避开了一些复杂的因素。其实,计算每个单元格的价值时,使用的公式都相同。 这个公式如下。

    你可以使用这个公式来计算每个单元格的价值,最终的网格将与前一个网格相同。现在你明 白了为何要求解子问题吧?你可以合并两个子问题的解来得到更大问题的解。

    二 背包问题FAQ

    2.1 再加一件商品如何

    假设你还选择一件商品:iPhone

    此时需要重新执行前面所做的计算吗?不需要。别忘了,动态规划 逐步计算最大价值。

    沿着一列往下走时,最大价值有可能降低吗?

    答案:不可能。每次迭代时,你都存储当前的最大价值。最大价值不可能比以前低!

    练习:假设你还可以选择——MP3播放器,它重1磅,价值1000美元。你会选择吗?

             不会。

    2.2 行的排列顺序发生变化时结果将如何

      假设你按如下顺序填充各行:音响、笔记本电脑、吉他。网格将会是什么样的?请自己动手填充这个网格,再接着往下读。

    答案没有变化。也就是说,各行的排列顺序无关紧要。

    2.3 可以逐列而不是逐行填充网格吗

    自己动手试试吧!

    这里推荐一个网站:http://karaffeltut.com/NEWKaraffeltutCom/Knapsack/knapsack.html

    2.4 增加一件更小的商品将如何呢

    需要重新调整网格,计算的单位更新如(0.5)。可以自己动手验证下。

    2.5 可以选择部分商品吗

    如果想这种情况下.只装商品的一部分。如何使用动态规划来处 理这种情形呢?

    答案是没法处理。使用动态规划时,要么考虑拿走整件商品,要么考虑不拿,而没法判断该不该拿走商品的一部分。

    但使用贪婪算法可轻松地处理这种情况!首先,尽可能多地拿价值最高的商品;如果拿光了, 再尽可能多地拿价值次高的商品,以此类推。

    2.6 旅游行程最优化

      假设你要去伦敦度假,假期两天,但你想去游览的地方很多。你没法前往每个地方游览,因此你列个单子。

    这也是一个背包问题!但约束条件不是背包的容量,而是有限的时间;不是决定该装入哪些 商品,而是决定该去游览哪些名胜。请根据这个清单绘制动态规划网格。

    当我在纸上画这个网格,逐个元素去填值计算的时候,边上的土豪QA妹子,应该不应这么纠结,多待两天都逛完了。可见钱能解决90%的问题。

    2.7 处理相互依赖的情况

    假设你还想去巴黎,因此在前述清单中又添加了几项。

    去这些地方游览需要很长时间,因为你先得从伦敦前往巴黎,这需要半天时间。如果这3个地方都去玩,是不是要4.5天呢?

    不是的,因为不是去每个地方都得先从伦敦到巴黎。到达巴黎后,每个地方都只需1天时间。

    因此玩这3个地方需要的总时间为3.5天(半天从伦敦到巴黎,每个地方1天),而不是4.5天。

    将埃菲尔铁塔加入“背包”后,卢浮宫将更“便宜”:只要1天时间,而不是1.5天。如何使 用动态规划对这种情况建模呢?

    没办法建模。动态规划功能强大,它能够解决子问题并使用这些答案来解决大问题。但仅当 每个子问题都是离散的,即不依赖于其他子问题时,动态规划才管用

    2.8 计算最终的解时会涉及两个以上的子背包吗

      但根据动态规划算法的设计,最多只需合并两个子背包,即根本不会涉及两个以上的子背包。不过这些子背包可能又包含子背包。

    2.9 最优解可能导致背包没装满吗

    完全可能,假设你选了一个3.5磅的钻石。

    练习:

    假设你要去野营。你有一个容量为6磅的背包,需要决定该携带下面的哪些东西。其中每样东西都有相应的价值,价值越大意味着越重要:

    我推导的结果:水+食物+相机=25

    最后附上一版本Java解决背包问题。

    /**
     * 
     * @author bohu83
     * @2019-06-11
     */
    public class FindMaxTest {
    	
    	static String[] names= {"","sound","laptop","guita","phone"};
    	static int[] w = {0,4, 3, 1,1 };//重量
    	static int[] v = {0,3000,2000,1500,2000}; //价值
        //包按照4磅重量算
    	static int[][] b = new int[5][5];
    
    
    	public static void main(String[] args) {
    		//一 先填充数据
            //遍历行:物品
            for (int i = 1; i <= 4; i++) {
            	//遍历列:重量
                for (int j = 1; j <= 4; j++) {
                	//装不进
                    if ( j< w[i] ) {
                        b[i][j] = b[i - 1][j];                
                    } else {//能装                	
                        int value1 = v[i] + b[i - 1][j - w[i]]  ; //当前商品的价值+剩余空间的价值
                        int value2 = b[i - 1][j]; // 上一单元格值
                        b[i][j] = Math.max(value1, value2);                    
                    }
                }
            }
            System.out.println("value:"+b[4][4]);
            findMax(4,4);
    	}
    	
    	/**
    	 * 寻找最大值对应的物品
    	 * @param i
    	 * @param j
    	 */
    	public static void findMax(int i,int j){
    		
    		if(i>0){
    			if(b[i][j]== b[i-1][j]){			
    				System.out.println("not choose :"+names[i]+",value="+v[i]);
    				findMax(i-1,j);
    			}
    			else if( b[i][j]==(v[i] + b[i - 1][j - w[i]]) ){			
    				System.out.println("choose :"+names[i]+",value="+v[i]);
    				findMax(i-1,j-w[i]);
    			}
    			
    		}
    		
    	}
    	
    }

    运行结果:

    背包问题已经解决,利用动态规划解决此问题的效率即是填写此张表的效率,所以动态规划的时间效率为O(number*capacity)=O(n*c),由于用到二维数组存储子问题的解,所以动态规划的空间效率为O(n*c)。

    注意下一些代码细节,例子画的网格图是为了便于理解,实际demo Java取的数组是从0开始的。所以数组的比图上的网格多加了一行,一列的0 的数组,无实际意义,纯粹为了填空格使用。还有网上有优化算法,二维数组转一维数组,只为了求值优化,但是不能找到最优组合选择的元素。感兴趣的可以试验下。

     

    展开全文
  • 有n件物品,每件物品的重量为w[i],其价值为v[i],现在有个有容量为m的背包,如何选择物品使得装入背包物品的价值最大。 先设置一个二维数组dp[ ][ ],令dp[i][j]表示前i个物品装进容量为j的背包能获得的最大价值。...
  • 背包问题是一类经典的动态规划问题,它非常灵活,需要仔细琢磨体会,本文先对背包问题的几种常见类型作一个总结,再给出代码模板,然后再看看LeetCode上几个相关题目。 根据维基百科,背包问题(Knapsack problem...
  • 问题描述:给定n种物品和一背包物品i的重量是wi,其价值是pi,背包的容量是M,问如何选择装入背包中的物品总价值最大?import java.util.ArrayList;import java.util.HashMap;/** 实际就是一种分而治之的思想*每次...
  • 动态规划——物品无限的背包问题

    千次阅读 2016-07-13 18:28:25
    物品无限的背包问题 物品无限的背包问题。有nn种物品,每种均有无穷多个。第i种物品的体积为ViV_i,重量为WiW_i。选一些物品装到一个容量为CC的背包中,使得背包物品在总体积不超过CC的前提下重量尽量大。1≤n≤...
  • 与分治法不同的是,动态规划分解得到的子问题往往不是互相独立的,即上一个子问题解可能为下一个子问题的条件(通常可以将结果填入表格) 背包问题 有一个背包容量为4kg,现在有以下物品 物体 重量 价格 ...
  • 背包问题是动态规划问题中最为经典的问题之一,可以说完全弄明白了背包问题,能够很大程度上帮助我们了解动态规划转移方程的基本推导。背包问题的经典讲义为浙江大学崔添翼同学撰写的《背包九讲》,本文是我阅读该...
  • 动态规划解决背包问题* 实验要求 给定n种物品和一个背包背包容量为X,物品i的重量为ai,价值为bi(i=1,2,3…)。编写一个动态规划程序,使背包内的物品价值最大。 实验过程 在解决找背包问题时,有以下几个步骤。 ...
  • 本算法用于背包问题动态规划算法,假设每种物品数量是不限的,最大体积为C时的所装最有价值物品
  • 动态规划就是将一个大问题不断向下拆分成小问题,直到拆分出的小问题可以出其解,然后将小问题的解不断的向上合并,最终得到大问题的解决方案。   2.01背包问题 一个旅行者有一个最多能装m公斤的背包,现在有n中...
  • 第一行两个整数,N,V,用空格隔开,分别表示物品数量背包容积。 接下来有 N 行,每行两个整数 vi,wi,用空格隔开,分别表示第 i 件物品的体积和价值。 输出格式 输出一行,包含若干个用空格隔开的整数,
  • 为了设计一个动态规划算法,需要分解问题,用部分物品组成的子问题的解来表示为背包问题的解: 首先,考虑一个由前 i 个物品(1 ≤ i ≤ n)定义的子问题物品的重量分别为 w1, w2, …, wi,价值分别为 v1, v2, ...
  • 最近又把背包系列问题温习了一遍,打算写篇文章将常见的几类背包问题进行总结,提取背包问题核心套路,在自己理解的同时,用通俗的语言解释,让看完本文的人能够快速上手解决一系列的背包问题。 内容包含如下: 从...
  • 基于动态规划方法求解0-1背包问题 一.题目 n个物品和1个背包。对物品i,其价值为vi,重量为wi,背包容量为W。如何选取物品装入背包,使背包中所装入的物品的总价值最大?其中,wi, W都是正整数。 二.分析 首先明确...
  • 编程语言:C语言 编程软件:Microsoft Visul C++ 6 操作系统:Windows 8.1 有5个物品,其重量分别是{2, 2, 6, 5, 4},价值分别为{6, 3, 5, 4, ...通过编程,学习用0-1背包动态规划和部分背包的贪婪算法解决以上问题
  • C语言动态规划——背包问题详解

    千次阅读 多人点赞 2021-04-22 21:53:33
    (质量) V[i](价值) 0 1 2 3 4 5 6 7 8 9 10 0 0 0 0 0 0 0 0 0 0 0 2 1 0 0 1 1 1 1 1 1 1 1 1 3 3 0 0 1 3 3 4 4 4 4 4 4 4 5 0 0 1 3 5 5 6 8 8 9 9 7 9 0 0 1 3 5 5 6 9 9 10 12 对于一个动态规划问题设置...
  • [python] 动态规划求解背包问题

    千次阅读 2018-08-12 18:06:43
    动态规划求解01背包   01背包问题描述: 01背包问题可以假设为现在有一堆物品,每一个物品都具有两个属性,物品的重量和价值。现在有一个承重有限的背包,给定背包的最大承受重量。现在要将物品装入背包,使得...
  • 动态规划:完全背包、多重背包

    万次阅读 多人点赞 2018-07-20 16:17:56
     完全背包:有N种物品和一个容量为V的背包,每种物品都有无限件可用。第i种物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。   多重背包:有N种...
  • 应用:1:该问题可以通过“局部寻优”逐步过渡到“整体最优”,这是贪心选择性质与“动态规划”的主要差别。2:最优子结构性质:某个问题的整体最优解包含了“子”问题的最优解。完整的代码如下: 代码如下:#include...
  • 如题所示: 01背包问题 时间限制: 1000 ms 内存限制: 65536 KB【题目描述】 一个旅行者有一个最多能装MM公斤的背包,现在有nn件物品,它们的重量分别是...=200)和NN(物品数量,N<=30N<=30); 第2..N+12...
  • 动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立...
  • 主要针对背包问题九讲中的第一讲:01背包问题进行了详细细致的说明。
  • 动态规划之01背包问题及其优化(python实现)

    万次阅读 多人点赞 2018-04-16 13:23:28
    动态规划之01背包问题及其优化(python实现) **背包问题(**Knapsack problem)是一种组合优化的NP完全问题问题描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得...
  • 基于01背包问题动态规划算法

    千次阅读 2020-08-12 00:31:59
    总结: 动态规划问题,大致可以通过以下四部进行解决。 1.划分状态,即划分子问题(核心思想) 2.状态表示,即如何让计算机理解子问题。(用二维数组表示最优决策表中每个子问题的解) 3.状态转移,即父问题是如何由...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 15,468
精华内容 6,187
关键字:

动态规划背包问题求物品数量