完全背包问题总结
完全背包问题-有N件物品和一个最多能背重量为W的背包
有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。
完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。
在下面的讲解中，我依然举这个例子：
背包最大重量为4。
物品为：
| 重量 | 价值 | |
|---|---|---|
| 物品0 | 1 | 15 |
| 物品1 | 3 | 20 |
| 物品2 | 4 | 30 |
每件商品都有无限个！
问背包能背的物品最大价值是多少？
解题思路
首先再回顾一下01背包的核心代码
01背包二维递推公式
//递推公式
dp[i][j] = Math.max(dp[i-1][j] , dp[i-1][j-weight[i]] + value[i]);
//其中dp[i][j]表示当前可装入0-i物品 背包容量为j的背包装入的最大价值
01背包一维递推公式
//递推公式
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
//我们使用滚动数组进行动态压缩后可得以上递推公式
我们知道01背包内嵌的循环是从大到小遍历，为了保证每个物品仅被添加一次。
所以其实完全背包问题的一二维递推表达式和01背包问题相同，而完全背包的物品是可以添加多次的
所以要从小到大去遍历，即：
// 先遍历物品，再遍历背包
for(int i = 0; i < weight.size(); i++) {
// 遍历物品
for(int j = weight[i]; j <= bagWeight ; j++) {
// 遍历背包容量
dp[i][j] = Math.max(dp[i-1][j] , dp[i-1][j-weight[i]] + value[i]);
//dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
解题模板
//先遍历物品，再遍历背包
private static void testCompletePack(){
int[] weight = {
1, 3, 4};
int[] value = {
15, 20, 30};
int bagWeight = 4;
int[] dp = new int[bagWeight + 1];
for (int i = 0; i < weight.length; i++){
// 遍历物品
for (int j = weight[i]; j <= bagWeight; j++){
// 遍历背包容量
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
}
}
for (int maxValue : dp){
System.out.println(maxValue + " ");
}
}
//先遍历背包，再遍历物品
private static void testCompletePackAnotherWay(){
int[] weight = {
1, 3, 4};
int[] value = {
15, 20, 30};
int bagWeight = 4;
int[] dp = new int[bagWeight + 1];
for (int i = 1; i <= bagWeight; i++){
// 遍历背包容量
for (int j = 0; j < weight.length; j++){
// 遍历物品
if (i - weight[j] >= 0){
dp[i] = Math.max(dp[i], dp[i - weight[j]] + value[j]);
}
}
}
for (int maxValue : dp){
System.out.println(maxValue + " ");
}
}
经典例题
力扣322.零钱兑换
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
示例 2：
输入：coins = [2], amount = 3
输出：-1
示例 3：
输入：coins = [1], amount = 0
输出：0
代码实现：
class Solution {
public int coinChange(int[] coins, int amount) {
//定义dp数组 dp[i]表示凑成金额为i的硬币所需的最少硬币个数
int[] dp = new int[amount+1];
int max = Integer.MAX_VALUE-1;
//初始化dp数组
for (int j = 0; j < dp.length; j++) {
dp[j] = max;
}
dp[0] = 0;
//因为是要找出最少的次数所以 遍历顺序不影响
for(int i=0;i<coins.length;i++){
for(int j=0;j<amount+1;j++){
//当背包容量大于等于硬币i的价值时 才能放入
if(j>=coins[i]){
//dp[j-coins[i]]表示当放入硬币i时剩余背包装满所需的最少硬币个数
dp[j] = Math.min(dp[j],dp[j-coins[i]]+1);
}
}
}
if(dp[amount]==max||dp[amount]<0){
return -1;
}
return dp[amount];
}
}
力扣518.零钱兑换II
给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
假设每一种面额的硬币有无限个。
题目数据保证结果符合 32 位带符号整数。
示例 1：
输入：amount = 5, coins = [1, 2, 5]
输出：4
解释：有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
示例 2：
输入：amount = 3, coins = [2]
输出：0
解释：只用面额 2 的硬币不能凑成总金额 3 。
示例 3：
输入：amount = 10, coins = [10]
输出：1
实现代码：
class Solution {
public int change(int amount, int[] coins) {
int count = 0;
//定义dp数组
int[] dp = new int[amount+1];
//这里初始化为1是方便后续计算 因为能装满背包的话 恰好得到dp[0] 这时我们需要让对应的dp[j]=1
dp[0] = 1;
//先遍历物品
for(int i=0;i<coins.length;i++){
//在遍历容量 j=coins[i]是因为 当背包容量大于等于硬币价值时才能放入
for(int j=coins[i];j<amount+1;j++){
//先固定拿物品i 然后放入背包中 就能到有多少种放满背包的方式了
dp[j] += dp[j-coins[i]];
}
}
return dp[amount];
}
}
力扣377.组合总和 Ⅳ
给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
题目数据保证答案符合 32 位整数范围。
示例 1：
输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。
示例 2：
输入：nums = [9], target = 3
输出：0
实现代码：
class Solution {
public int combinationSum4(int[] nums, int target) {
//定义dp数组 dp[i] 表示总和为i一共有dp[i]种方法
int[] dp = new int[target+1];
//初始化dp数组
dp[0] = 1;
//因为本题强调了结果的排序性 所以我们先遍历背包在遍历物品求排列
//先遍历背包
for(int i=0;i<target+1;i++){
//在遍历物品
for(int j=0;j<nums.length;j++){
if(i>=nums[j]){
//dp[1] = 1 dp[2] = 2
dp[i] += dp[i-nums[j]];
}
}
}
for(int i=0;i<dp.length;i++){
System.out.print(dp[i]);
}
return dp[target];
}
}
力扣279.完全平方数
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
示例 1：
输入：n = 12
输出：3
解释：12 = 4 + 4 + 4
示例 2：
输入：n = 13
输出：2
解释：13 = 4 + 9
代码实现：
class Solution {
public int numSquares(int n) {
//定义dp数组 dp[i] 表示返回和为i的最少数量
int[] dp = new int[n+1];
//初始化dp数组
int max = Integer.MAX_VALUE;
for(int i=0;i<dp.length;i++){
dp[i] = max;
}
dp[0] = 0;
//遍历dp数组 因为题目强调的是求最少数量 因此遍历顺序都可
//先遍历金额
for(int i=1;i*i<=n;i++){
//在遍历背包 为什么j=i*i
//是因为如果j<i*i的话会导致j-i*i为负数 而dp[j-i*i]如果下标为负数则会报错
for(int j=i*i;j<n+1;j++){
//只有当放入这个数后剩余背包能放下的数量不为max才有意义 不然无法组成n
if(dp[j-i*i]!=max){
dp[j] = Math.min(dp[j],dp[j-i*i]+1);
}
}
}
return dp[n];
}
}
力扣139.单词拆分
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
**注意：**不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
示例 1：
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
示例 2：
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
注意，你可以重复使用字典中的单词。
示例 3：
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false
实现方法：
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
//定义dp数组 dp[i]表示从0-i区间的满不满足条件 若满足条件设为true不满足为false
boolean[] dp = new boolean[s.length()+1];
//利用hashset来去重
HashSet<String> set = new HashSet<>(wordDict);
//初始化dp数组
dp[0] = true;
//遍历
for(int i=0;i<s.length()+1;i++){
for(int j=0;j<i;j++){
//如果截取下来的字符串能匹配到 并且他截取之前的串也满足条件 那么他们俩都满足条件
if(set.contains(s.substring(j,i)) && dp[j]){
dp[i] = true;
}
}
}
return dp[s.length()];
}
}
小结
零钱兑换问题中，要求出装满背包所需的最少硬币个数，装不满则返回-1
首先考虑，要当背包容量即总金额大于硬币价值我们才能进行兑换
在这道题中值得留意的是，我们每放入一个硬币则需要让dp数组值+1 而不是以往的加入硬币价值
零钱兑换II，组合总和问题中，就是给你一堆零钱（零钱个数无限），为凑成amount的组合数有几种。
注意这里组合数和排列数的区别！（排列强调顺序性，组合不强调）
这里在遍历顺序上可就有说法了。
- 如果求组合数就是外层for循环遍历物品，内层for遍历背包。
- 如果求排列数就是外层for遍历背包，内层for循环遍历物品。
完全平方数这道题求的是给定正整数 n，找到若干个完全平方数使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
所以类似于零钱兑换II问题，不过这次我们不是放的硬币价值了 而是放的硬币价值的平方，将递推式稍微修改即可
单词拆分这道题我们要想到本题其实我们求的是排列数，为什么呢？
拿 s = “applepenapple”, wordDict = [“apple”, “pen”] 举例。
“apple”, “pen” 是物品，那么我们要求 物品的组合一定是 “apple” + “pen” + “apple” 才能组成 “applepenapple”。
“apple” + “apple” + “pen” 或者 “pen” + “apple” + “apple” 是不可以的，那么我们就是强调物品之间顺序。
所以说，本题一定是 先遍历 背包，再遍历物品
其中一定要深刻理解dp[i]表示的是截取s字符串0-i区间是否可以组成，在此基础上我们在判断新截取的那个字符我们能否在set集合中找到
多重背包问题
有N种物品和一个容量为V 的背包。第i种物品最多有Mi件可用，每件耗费的空间是Ci ，价值是Wi 。求解将哪些物品装入背包可使这些物品的耗费的空间 总和不超过背包容量，且价值总和最大。
多重背包和01背包是非常像的， 为什么和01背包像呢？
每件物品最多有Mi件可用，把Mi件摊开，其实就是一个01背包问题了。
例如：
背包最大重量为10。
物品为：
| 重量 | 价值 | 数量 | |
|---|---|---|---|
| 物品0 | 1 | 15 | 2 |
| 物品1 | 3 | 20 | 3 |
| 物品2 | 4 | 30 | 2 |
问背包能背的物品最大价值是多少？
和如下情况有区别么？
| 重量 | 价值 | 数量 | |
|---|---|---|---|
| 物品0 | 1 | 15 | 1 |
| 物品0 | 1 | 15 | 1 |
| 物品1 | 3 | 20 | 1 |
| 物品1 | 3 | 20 | 1 |
| 物品1 | 3 | 20 | 1 |
| 物品2 | 4 | 30 | 1 |
| 物品2 | 4 | 30 | 1 |
毫无区别，这就转成了一个01背包问题了，且每个物品只用一次。
public static void main(String[] args) {
int[] weight = {
1, 3, 4};
int[] value = {
15, 20, 30};
int[] nums = {
1,2,2};
int bagWight = 4;
testWeightBagProblem(weight, value, bagWight);
}
public static void testWeightBagProblem(int[] weight, int[] value, int bagWeight){
int wLen = weight.length;
//定义dp数组：dp[j]表示背包容量为j时，能获得的最大价值
int[] dp = new int[bagWeight + 1];
//遍历顺序：先遍历物品，再遍历背包容量
for (int i = 0; i < wLen; i++){
//这里注意 使用一维数组解决01背包问题 背包大小需要倒序遍历以避免重复获取物品
for (int j = bagWeight; j >= weight[i]; j--){
//这里遍历物品的数量 是把多重背包问题转化为01背包的关键
for (int k = 1; k <= nums[i] && (j - k * weight[i]) >= 0; k++) {
// 遍历个数
dp[j] = max(dp[j], dp[j - k * weight[i]] + k * value[i]);
}
}
}
//打印dp数组
for (int j = 0; j <= bagWeight; j++){
System.out.print(dp[j] + " ");
}
}
从代码里可以看出是01背包里面在加一个for循环遍历一个每种商品的数量。 和01背包还是如出一辙的。
