代码随想录刷题| 多重背包理论基础、背包问题的总结

简介: 代码随想录刷题| 多重背包理论基础、背包问题的总结

多重背包理论基础

多重背包的问题

  • 有N种物品和一个容量为V 的背包。第i种物品最多有Mi件可用,每件耗费的空间是Ci ,价值是Wi 。求解将哪些物品装入背包可使这些物品的耗费的空间 总和不超过背包容量,且价值总和最大

多重背包的解法


  • 多重背包问题可以使用01背包的思路去解决
  • 既然物品的数量是固定,就可以使用01背包,只不过其中的物品有重复
  • 假设现在有个背包如下:

33091904585f44138c4f7403152ce064.png

  • 可以将这个多重背包转换成:

6c60b44a85234228926a325c0da23db4.png

  • 这就可以看成一个01背包问题了


多重背包的代码

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class MultiBagProblem {
    public static void main(String[] args) {
        // 物品信息
        /**
         *          重量  价值  数值
         *  物品0     1    15    2
         *  物品1     3    20    3
         *  物品2     4    20    2
         */
        List<Integer> weight = new ArrayList<>(Arrays.asList(1,3,4));
        List<Integer> value = new ArrayList<>(Arrays.asList(15,20,30));
        List<Integer> nums = new ArrayList<>(Arrays.asList(2,3,3));
        // 背包信息
        int bagSize = 10;
        multiBag(weight,value,nums,bagSize);
    }
    /**
     *
     * @param weight  物品的重量
     * @param value   物品的价值
     * @param nums    物品的数量
     * @param bagSize 背包的容量
     */
    private static void multiBag(List<Integer> weight,
                          List<Integer> value,
                          List<Integer> nums,
                          int bagSize) {
        /**
         * 将物品展开
         */
        // 先把物品展开,展开成一个物品只有一个
        for (int i = 0; i < nums.size(); i++) {
            while (nums.get(i) > 1) {
                weight.add(weight.get(i));
                value.add(value.get(i));
                nums.set(i , nums.get(i) - 1);   // 展开一个,原数量就减一
            }
        }
        /**
         * 按照01背包进行装包
         */
        // 创建dp数组
        int[] dp = new int[bagSize+1];
        // 遍历更新dp数组
        for (int i = 0; i < weight.size(); i++) {  // 先对物品进行遍历
            for (int j = bagSize; j >= weight.get(i); j--) {  // 再对背包进行倒序遍历
                dp[j] = Math.max(dp[j],dp[j-weight.get(i)] + value.get(i));
            }
            // 打印dp数组
            System.out.println("物品" + i + "\t" + Arrays.toString(dp));
        }
    }
}


背包问题的总结

01背包


01背包是重中之重

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

主要有以下几种问题:

1、求物品装进背包中的最大价值(纯01背包)

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

对应的题目

416.分割等和子集

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

2、求物品装满背包的方法数

递推公式原理为:dp[ j ] += dp[ j - weight[ i ] ]

由于方法数是逐步积累的,所以初始化应该是dp[ 0 ] = 1

对应的题目

494.目标和

3、求最终背包中的物品数

递推公式原理为:dp[ j - weight[ i ] + 1]

如果是求最大个数:就是dp[ j ] = max(dp[ j ],dp[ j - weight[ i ] ] + 1 );由于是求最大值,初始化时dp[0] = 0,其余的也为0。对应的题目有 474.一和零

如果是求最小个数:就是dp[ j ] = min(dp[ j ],dp[ j - weight[ i ] ] + 1 );由于是求最小值,初始化时dp[0] = 0,其余的为MAX_VALUE。对应的题目有 322.零钱兑换


完全背包


01背包的时候,为了使物品在向背包中添加的时候保证物品只添加一次,在遍历背包的时候使用倒序遍历

那完全背包中的物品是可以被重复添加的,那么在遍历背包的时候使用正序遍历,就可以保证物品被多次添加

主要有以下几种问题

1、求物品装进背包中的最大价值(纯完全背包)

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

2、求物品装满背包的方法数

递推公式原理为:dp[ j ] += dp[ j - weight[ i ] ]

由于方法数是逐步积累的,所以初始化应该是dp[ 0 ] = 1

对应的题目

518.零钱兑换|| —— 求组合数 —— 先遍历物品再遍历背包

377.组合总和IV —— 求排列数 —— 先遍历背包再遍历物品

70.爬楼梯 —— 求排列数 —— 先遍历背包再遍历物品

3、求最终背包中的物品数

递推公式原理为:dp[ j - weight[ i ] + 1]

如果是求最小个数:就是dp[ j ] = min(dp[ j ],dp[ j - weight[ i ] ] + 1 );由于是求最小值,初始化时dp[0] = 0,其余的为MAX_VALUE

对应的题目

322.零钱兑换

279.完全平方数


多重背包

  • 多重背包的解决方案就是将多重背包转换成01背包进行处理
  • 原理上并没有什么难点,等遇到相应的题目再说


相关文章
牛客刷题之数学基础-快速幂
牛客刷题之数学基础-快速幂
59 0
|
7月前
|
算法
六六力扣刷题贪心算法之基础和最大子序和
六六力扣刷题贪心算法之基础和最大子序和
44 0
|
算法
代码随想录Day20 回溯算法 LeetCode77 组合问题
代码随想录Day20 回溯算法 LeetCode77 组合问题
36 0
[算法刷题题解笔记] 洛谷 P1007 独木桥 [贪心]
[算法刷题题解笔记] 洛谷 P1007 独木桥 [贪心]
|
机器学习/深度学习 算法
LeetCode刷题系列(一)把回溯算法框架将给爷爷奶奶听(下)
LeetCode刷题系列(一)把回溯算法框架将给爷爷奶奶听(下)
|
算法
LeetCode刷题系列(一)把回溯算法框架将给爷爷奶奶听(上)
LeetCode刷题系列(一)把回溯算法框架将给爷爷奶奶听(上)
|
算法
LeetCode刷题系列(一)把回溯算法框架将给爷爷奶奶听(中)
LeetCode刷题系列(一)把回溯算法框架将给爷爷奶奶听(中)
|
算法 Java
数据结构与算法之打家劫舍(二)&&动态规划思想
数据结构与算法之打家劫舍(二)&&动态规划思想
108 0
数据结构与算法之打家劫舍(二)&&动态规划思想
|
算法 Java C++
数据结构与算法之打家劫舍(一)&&动态规划思想
数据结构与算法之打家劫舍(一)&&动态规划思想
113 0
数据结构与算法之打家劫舍(一)&&动态规划思想
|
存储 机器学习/深度学习 算法
算法刷题第十二天:动态规划
空间复杂度:O(1)。使用滚动数组,可以只存储前两间房屋的最高总金额,而不需要存储整个数组的结果,因此空间复杂度是O(1)。
116 0
算法刷题第十二天:动态规划