目录

多重背包理论基础

多重背包的问题

多重背包的解法

多重背包的代码

背包问题的总结

01背包

完全背包

多重背包

多重背包理论基础

多重背包的问题

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

多重背包的解法

• 多重背包问题可以使用01背包的思路去解决
• 既然物品的数量是固定，就可以使用01背包，只不过其中的物品有重复
• 假设现在有个背包如下：
  
• 可以将这个多重背包转换成：
  
• 这就可以看成一个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 weight = new ArrayList<>(Arrays.asList(1,3,4));List value = new ArrayList<>(Arrays.asList(15,20,30));List 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 weight,List value,List 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背包进行处理
• 原理上并没有什么难点，等遇到相应的题目再说