完全背包

发表于2024-07-01更新于2024-07-09

完全背包

什么是完全背包

  • 01背包，每个物品只能使用一次
  • 完全背包：每个物品可以使用无数次

图 0

01背包引出完全背包

1
2
3
4
5
for (let i=0;i<goodsNum;i++){
  for (let j=weight[i];j<=bagWeight;j--){
    dp[j] = max(dp[j],dp[j-weight[i]]+value[i])
  }
}
  • 01背包使用一维滚动数组时，背包容量要倒序遍历，这样保证每个物品只是用一次。
  • 完全背包，物品可以使用无数次，因此将背包容量遍历的时候改为正序遍历，即可实现

图 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//ACM模式
let readline = require('readline')
const rl = readline.createInterface({
    input:process.stdin,
    output:process.stdout
});
let inputArr = []
 rl.on('line',function(line){
     inputArr.push(line.split(' '))
 }).on('close',function(){
     let n = parseInt(inputArr[0][0])
     let v = parseInt(inputArr[0][1])
     let weight = []
     let value = []
     for (let i = 1;i<=n;i++){
         weight.push(parseInt(inputArr[i][0]))
         value.push(parseInt(inputArr[i][1]))
     }
     let dp = Array(v+1).fill(0)
     for (let i=0;i<=n;i++){
      //这边这个循环要注意，总写错j的起始值
         for(let j=weight[i];j<=v;j++){
            dp[j] = Math.max(dp[j],dp[j-weight[i]]+value[i])
         }
     }
     console.log(dp[v])
 })

题目

零钱兑换

https://leetcode.cn/problems/coin-change-ii/description/

图 2

思路
这是一个统一方法数的题目，和之前价值不一样的递推公式。

  • bn找价值最高：max(dp[j],dp[j]+dp[j-weight[i]]+value[i])
  • 而找方法数：dp[j]+=dp[j-weight[i]]
    就比如硬币找零：找总额5元,有1，2，5三种硬币，那么dp[5] = dp[4] + dp[3] + dp[0]

五部曲
1、dp[j] 表示总和为j的找零方式；
2、递推公式 dp[j] += dp[j-coins[i]]；
3、初始化，dp[0] = 1,其他索引对应的值均为0,因为要加等于，如果都是零加起来也都是零；
4、遍历，两个都是正序，因为完全背包，每种面额的钱有无数张。
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
因为则何种情况下物品的遍历顺序是固定的，有{1,2}就没有被{2,1}

1
2
3
4
5
6
7
8
9
10
11
12
var change = function(amount, coins) {
  let n = amount
  let m = coins.length
  let dp = Array(n+1).fill(0)
  dp[0] = 1
  for (let i=0;i<m;i++){
    for(let j = coins[i];j<=n;j++){
      dp[j] += dp[j-coins[i]]
    }
  }
  return dp[n]
};

组合总和IV

https://leetcode.cn/problems/combination-sum-iv/description/

图 3

题目实际上是一个排列问题，元素有顺序的要求了，所以遍历顺序是解题关键

动规五部曲
1、dp[j]表示目标为j时的排列数量
2、递推公式：算方法数dp[j] += dp[j-nums[i]]
3、初始化，dp[0]=1,其他均为零
4、遍历，先遍历背包后遍历物品这样物品就有顺序了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var combinationSum4 = function(nums, target) {
  let n = target
  let m = nums.length
  let dp = Array(n+1).fill(0)
  dp[0] = 1
  // 背包
  for (let i=0;i<=n;i++){
    // 物品
    for (let j=0;j<m;j++){
      if (i-nums[j] >=0)  dp[i] += dp[i - nums[j]]
    }
  }
  return dp[n]
};

爬楼梯(进阶版)

https://kamacoder.com/problempage.php?pid=1067

图 4

思路
使用动规五部曲分析

  • 1、dp[i]表示爬到第i级台阶的方法数
  • 2、递推公式：dp[i] = dp[i-1] + dp[i-2] + … +dp[i-m]
  • 3、初始化：
    需要初始化dp[0]到dp[m]，但是m是变化的，不能直接赋值需要一步步递推。
    以m为5的情况为例：
    dp[1] = 1
    dp[2] = dp[1] + 1
    dp[3] = dp[2] + dp[1] + 1
    dp[4] = dp[3] + dp[2] + dp[1] +1
    dp[5] = dp[4] + dp[3] +dp[2] + dp[1] +1
    根据上述规律不难想出，让dp[0] = 1
    此外还可以看出这里的规律和递推公式是如出一辙
    dp[j] = dp[j-1] + dp[j-2] + … dp[j-m]
  • 4、遍历顺序：外层遍历爬上的太结束，内层遍历m
    综上得出如下面的代码。

总结
看了代码随想录的文档，惊觉这竟然是一个完全背包问题。其中要爬最终台阶个数为背包容量；而能爬的台阶个数1，2，… m是物品数量。

每次爬的台阶数可以重复也就是物品可以重复放。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const readline = require('readline')
const rl = readline.createInterface({
    input:process.stdin,
    output:process.stdout
});

rl.on('line',function(line){
    var tokens = line.split(' ')
    let n = parseInt(tokens[0])
    let m = parseInt(tokens[1])
    let dp = Array(n+1).fill(0)
    dp[0] = 1
    for (let i=0;i<=n;i++){
        for (let j=1;j<=m && i-j>=0;j++){
            dp[i] += dp[i-j]
        }
    }
    console.log(dp[n])
})

零钱兑换（322）

https://leetcode.cn/problems/coin-change/description/

图 5

思路
*1、dp[i] 表示兑换总额为i的金钱需要的最少硬币数
*2、递推公式 dp[j] = min(dp[j],dp[j-coins[i]]+1)
*3、初始化 dp[0] = 0,其余均为一个较大的正整数
*4、遍历顺序：先遍历物品后遍历背包，背包容量从小到。

记错模块
dp数组及其下标的含义、递推公式以及初始化都是没有问题的，但是在遍历顺序上我搞反了，导致错误。组合问题还是要先遍历物品，这样物品有顺序。排列问题才需要物品顺序的变化，要先遍历背包。

图 6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var coinChange = function(coins, amount) {
  let n = amount
  let m = coins.length
  let dp = Array(n+1).fill(Number.MAX_SAFE_INTEGER)
  dp[0] = 0
  for(let i=0;i<m;i++){
    console.log(dp)
    for(let j=coins[i];j<=n;j++){
      dp[j] = Math.min(dp[j],dp[j-coins[i]]+1)

    }
  }
  if (dp[n] == Number.MAX_SAFE_INTEGER) return -1
  else return dp[n]
};

完全平方数

https://leetcode.cn/problems/perfect-squares/description/

图 7

思路
感觉这个和前一道题也没啥区别，只不过需要自己简历完全平方数的数组而已。物品是一个个的完全平方数，背包就是和。
*1、dp[i],表示组成和为i的完全平方数的个数
*2、递推公式，dp[j] = min(dp[j],dp[j-nums[i]]+1)
*3、初始化，dp[0] = 0,其他值为最大正整数
*4、遍历顺序，先遍历物品，后遍历背包，背包正序遍历。

1
2
3
4
5
6
7
8
9
10
11
12
var numSquares = function(n) {
  let m = Math.floor(Math.sqrt(n))
  const num = Array.from({ length: m }, (_, i) => (i + 1) ** 2)
  let dp = Array(n+1).fill(Number.MAX_SAFE_INTEGER)
  dp[0] = 0
  for(let i=0;i<m;i++){
    for(let j = num[i];j<=n;j++){
      dp[j] = Math.min(dp[j],dp[j-num[i]]+1)
    }
  }
  return dp[n]
};

单词拆分

https://leetcode.cn/problems/word-break/description/

图 8

思考
难点：背包是什么，背包装满怎么表示？
背包是指字符串s，s能否用数组中的单词表示就是能否装满的意思。

*1、dp[i]表示字符串s[0:i]能否由数组组成
*2、递推公式：i表示背包，j表示物品索引
q = i-wordDict(j)
dp[i] = (dp[q] && s[q,i] === wordDictus[j])
*3、初始化，dp[0] = true,其他为false
*4、这本质上是一个求排列的问题，所以要先遍历背包i后后遍历物品j。

记错模块
直接在内循环中使用dp[i] = dp[q] && s.substring(q, i) === wordDict[j]
则会么写的问题在于忽略了三个问题
*首先i-wordDict[j]的大小是否大于0
*每遍历一个单词dp[i]都要被修改，如果已经找到了单词满足条件，继续遍历，答案势必会错
*substring的用法,应该是小括号

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var wordBreak = function(s, wordDict) {
  let n = s.length
  let m = wordDict.length
  let dp = Array(n+1).fill(false)
  dp[0] = true
  console.log(dp)
  for(let i=0;i<=n;i++){
    for(let j = 0;j<m;j++){
      //这里忘记打.length了
      let q = i-wordDict[j].length
      if (q >= 0 && dp[q] && s.substring(q, i) === wordDict[j]) {
        dp[i] = true;
        break; // 找到匹配，无需继续检查其他单词
      }
      console.log(dp)
    }
  }
  return dp[n]
};