背包做题笔记
tbghg

你的背包~🎵

前言

这个是刷代码随想录的做题笔记,分析部分大多是我自己的理解,代码我用go写的,现在回头再看一遍还是觉得代码随想录总结的很棒,强推一波!

背包概括

image

面试的话,其实掌握 01背包 完全背包,就够用了,leetcode上连多重背包的题目都没有

完全背包又是也是01背包稍作变化而来,即:完全背包的物品数量是无限的。01背包是基础,需要重点掌握。

01背包

01背包初介绍

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

先从暴力的角度来看,通过回溯实现暴力,每一件物品其实只有两个状态,取或者不取,所以可以使用回溯法搜索出所有的情况,那么时间复杂度就是o(2^n),这里的n表示物品数量。

所以暴力的解法是指数级别的时间复杂度。进而才需要动态规划的解法来进行优化

入门例题

背包最大重量为4,物品为:

重量 价值
物品0 1 15
物品1 3 20
物品2 4 30

问背包能背的物品最大价值是多少?

分析

动规五部曲

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

对于背包问题,有一种写法, 是使用二维数组,即dp[i][j] 表示从下标为[0-i]的物品里任意取,放进容量为j的背包,价值总和最大是多少

0 1 2 3 4
物品0
物品1
物品2
  1. 确定递推公式

再回顾一下dp[i][j]的含义:从下标为[0-i]的物品里任意取,放进容量为j的背包,价值总和最大是多少

那么可以有两个方向推出来dp[i][j]:

  • 不放物品i:由dp[i - 1][j]推出,即背包容量为j,里面不放物品i的最大价值,此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量时,物品i无法放进背包中,所以被背包内的价值依然和前面相同)
  • 放物品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])

  1. dp数组如何初始化

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

0 1 2 3 4
物品0 0
物品1 0
物品2 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的物品的时候,各个容量的背包所能存放的最大价值

0 1 2 3 4
物品0 0 15 15 15 15
物品1 0
物品2 0

首先j=0(容量为0)这里是可以初始值不用管的,并且根据遍历顺序来说也是不用管,这个后面会看到

初始化的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func main() {
weight := []int{1, 3, 4}
value := []int{15, 20, 30}
bigWeight := 4
dp := make([][]int, len(weight))
for i := 0; i < len(weight); i++ {
// 因为容量包含0,所以要+1
dp[i] = make([]int, bigWeight+1)
}
// 这里直接从weight[0]起步,前面的肯定是0
for j := weight[0]; j <= bigWeight; j++ {
dp[0][j] = value[0]
}
fmt.Println(dp)
}
// output:[[0 15 15 15 15] [0 0 0 0 0] [0 0 0 0 0]]
  1. 确定遍历顺序

01背包遍历顺序两种都行,但是先遍历物品更好理解

1
2
3
4
5
6
7
8
9
10
11
12
13
// 遍历物品
for i := 1; i < len(weight); i++ {
// 遍历容量
for 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])
}
}
}
fmt.Println(dp)
//output:[[0 15 15 15 15] [0 15 15 20 35] [0 15 15 20 35]]

滚动数组空间优化

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

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

动规五部曲

  1. 确定dp数组的定义

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

  1. dp数组的递推公式
1
dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
  1. dp数组初始化

dp[0]=0,其他情况下可以通过dp[0]直接横着推过来

  1. 遍历顺序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func main() {
weight := []int{1, 3, 4}
value := []int{15, 20, 30}
bagWeight := 4
// 因为容量包含0,所以要+1
dp := make([]int, bagWeight+1)
// 遍历物品
for i := 0; i < len(weight); i++ {
// 遍历容量
for j := bagWeight; j >= weight[i]; j-- {
dp[j] = max(dp[j], dp[j-weight[i]]+value[i])
}
}
fmt.Println(dp)
}
//output:[0 15 15 20 35]

这块是重点,注意:必须先遍历物品再遍历背包必须倒序遍历

先遍历物品再遍历背包:因为一维dp的写法,背包容量一定是要倒序遍历,如果遍历背包容量放在上一层,那么每个dp[j]就只会放入一个物品,即:背包里只放入了一个物品(举个例子自己走一遍就差不多理解了)

倒顺遍历:无法知道物品装了没装,容易装多次,倒着来的话本容量下前面的肯定没装该物品,因为还没遍历到

分割等和子集

题目链接

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

示例 1:

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

示例 2:

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

提示:

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 100

分析

[1,5,11,5]为例,和为22,相当于一个11的背包看看最多可以装多少个,如果小于11输出false,等于11输出true,一道简单的01背包问题

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func canPartition(nums []int) bool {
var sum int
for _, v := range nums {
sum += v
}
if sum%2 != 0 {
return false
}
sum /= 2
dp := make([]int, sum+1)
for i := 0; i < len(nums); i++ {
for j := sum; j >= nums[i]; j-- {
dp[j] = max(dp[j], dp[j-nums[i]]+nums[i])
}
}
return dp[sum] == sum
}

func max(a, b int) int {
if a > b {
return a
}
return b
}

最后一块石头的重量 II

题目链接

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

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

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

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

示例 1:

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

示例 2:

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

提示:

  • 1 <= stones.length <= 30
  • 1 <= stones[i] <= 100

分析

乍一看一脸懵逼,仔细想想的话反正一个是加数一个是减数,分成两拨来碰,和上面那道题好像一样:一组数,分两拨,两拨之间差值如何最小,输出即可,那也就相当于一组数,sum/2为容量,看看最大是多少,最后输出sum/2-该数

但是需要考虑sum%2为1的情况,以sum=9为例,肯定有一波小于等于4,一波小于等于5,不管是哪一波,一个向中间聚拢,另一个也是,所以背包容量取哪个都没影响。我们可以直接向下取整,因为sum/2就是,并且容量小的话for层数也少。

因为背包容量算出来的是小于等于sum/2的,并且还有可能向下取整,所以最后结果为sum-dp[bagWeight] - dp[bagWeight]

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func lastStoneWeightII(stones []int) int {
var sum int
for _, stone := range stones {
sum += stone
}
bagWeight := sum / 2
dp := make([]int, bagWeight+1)
// 遍历物品
for i := 0; i < len(stones); i++ {
// 遍历容量
for j := bagWeight; j >= stones[i]; j-- {
dp[j] = max(dp[j], dp[j-stones[i]]+stones[i])
}
}
return sum - dp[bagWeight]*2
}

目标和

给你一个整数数组 nums 和一个整数 target

向数组中的每个整数前添加 '+''-' ,然后串联起所有整数,可以构造一个 表达式

  • 例如,nums = [2, 1] ,可以在 2 之前添加 '+' ,在 1 之前添加 '-' ,然后串联起来得到表达式 "+2-1"

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

示例 1:

1
2
3
4
5
6
7
8
输入: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

示例 2:

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

提示:

  • 1 <= nums.length <= 20
  • 0 <= nums[i] <= 1000
  • 0 <= sum(nums[i]) <= 1000
  • -1000 <= target <= 1000

分析

这道题比较难想,但是有过这一次之后以后同类型的会好很多。

加号的分为一波,减号的分为一波,假设加法的总和为x,那么减法对应的总和就是sum - x。所以我们要求的是 x - (sum - x) = target,x = (target + sum) / 2

此时问题就转化为,装满容量为x的背包,有几种方法

bagSize就是(target + sum) / 2 ,如果这个数不能整除,那就不可能凑不来方法,return 0即可

这次和之前遇到的背包问题不一样了,之前都是求容量为j的背包,最多能装多少。本题则是装满有几种方法。其实这就是一个组合问题

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

dp[j] 表示:填满j(包括j)这么大容积的包,有dp[j]种方法

  1. 确定递推公式

dp[j],j 为5

  • 已经有一个1(nums[i]) 的话,有 dp[4]种方法 凑成 容量为5的背包。
  • 已经有一个2(nums[i]) 的话,有 dp[3]种方法 凑成 容量为5的背包。
  • 已经有一个3(nums[i]) 的话,有 dp[2]中方法 凑成 容量为5的背包
  • 已经有一个4(nums[i]) 的话,有 dp[1]中方法 凑成 容量为5的背包
  • 已经有一个5 (nums[i])的话,有 dp[0]中方法 凑成 容量为5的背包

那么凑整dp[5]有多少方法呢,也就是把 所有的 dp[j - nums[i]] 累加起来。

所以求组合类问题的公式,都是类似这种:

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

这个公式在后面在讲解背包解决排列组合问题的时候还会用到!

  1. dp数组如何初始化

从0开始推,容量为0装满的方式有1种,这个是初始值,其他通过这个推过来。

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

  1. 确定遍历顺序

一维dp数组,先物品再容量

代码

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
func findTargetSumWays(nums []int, target int) int {
sum := target
for _, num := range nums {
sum += num
}
if sum%2 == 1 {
return 0
}
bagWeight := sum / 2
// 这里需要判断bagWeight是否小于0
// 例如 [100],-200 的输入
if bagWeight < 0 {
return 0
}
// dp[j] 表示:填满j这么大容积的包,有dp[j]种方法
dp := make([]int, bagWeight+1)
dp[0] = 1
for i := 0; i < len(nums); i++ {
for j := bagWeight; j >= nums[i]; j-- {
dp[j] += dp[j-nums[i]]
}
}
fmt.Println(dp)
return dp[bagWeight]
}

一和零

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

请你找出并返回 strs 的最大子集的长度,该子集中 最多m0n1

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

示例 1:

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

示例 2:

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

提示:

  • 1 <= strs.length <= 600
  • 1 <= strs[i].length <= 100
  • strs[i] 仅由 '0''1' 组成
  • 1 <= m, n <= 100

分析

这个题其实不难看出来是01背包问题但是有两个维度限制(经常见这类型的题),就像有的大招既扣蓝也扣血,这俩都算是背包的容量,所以我们for循环遍历需要三层了:物品、容量0、容量1(我们需要把dp[m][n]中,m、n取值的各种情况都填满!

创建dp数组的时候再多创建一个维度即可,例如我们用滚动数组,一维数组即可解决,这里要变成二维

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

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

  1. 确定递推公式

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

此时大家可以回想一下01背包的递推公式:dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

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

  1. dp数组如何初始化

根据含义dp[0][0]直接为0就行,滚动数组的话也不会覆盖掉什么的

  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
func findMaxForm(strs []string, m int, n int) int {
// 滚动数组,所以 创建dp数组时无需考虑物品的容量
// 因为是两个容量限制,所以是dp[m+1][n+1] (加一是因为含有0)
dp := make([][]int, m+1)
for i := 0; i <= m; i++ {
dp[i] = make([]int, n+1)
}
// 遍历物品
for _, str := range strs {
zeroNum,oneNum := 0,0
for _, ch := range str {
if ch == '0' {
zeroNum++
} else {
oneNum++
}
}
// 遍历容量
for i := m; i >= zeroNum; i-- { // 遍历0的容量
for j := n ; j >= oneNum; j-- { // 遍历1的容量
dp[i][j] = max(dp[i][j],dp[i-zeroNum][j-oneNum]+1)
}
}
}
return dp[m][n]
}

01背包总结

刚刚刷过的题目总结一下:

所以在代码随想录中所列举的题目,都是 0-1背包不同维度上的应用

【不得不说卡哥找的这些题都太典型了,每道题是一种类型,有些佩服】

完全背包

概述

完全背包和01背包问题唯一不同的地方就是,每种物品有无限件

以例题为切入,背包最大重量为4,物品如下:

重量 价值
物品0 1 15
物品1 3 20
物品2 4 30

每件商品都有无限个,问背包能背的物品最大价值是多少?

回顾一下01背包的核心代码:

1
2
3
4
5
6
7
// 遍历物品
for i := 0; i < len(weight); i++ {
// 遍历容量
for j := bagWeight; j >= weight[i]; j-- {
dp[j] = max(dp[j], dp[j-weight[i]]+value[i])
}
}

其中容量倒序遍历,为了保证每个物品仅被添加一次,而完全背包的物品是可以添加多次的,所以要从小到大去遍历,即:

1
2
3
4
5
6
7
// 遍历物品
for i := 0; i < len(weight); i++ {
// 遍历容量
for j := weight[i]; j <= bagWeight; j-- {
dp[j] = max(dp[j], dp[j-weight[i]]+value[i])
}
}

01背包中必须先遍历物品,再遍历容量,但完全背包中两种遍历方式都可以,因为dp[j]是根据 下标j之前所对应的dp[j]计算出来的,只要保证下标j之前的dp[j]都是经过计算的就可以了,而完全背包从前往后遍历,所以前面的数都是全的,咋遍历都没问题。

背包遍历顺序

  • 01背包:先物品后容量,容量倒序遍历
  • 完全背包:容量正序遍历,两种遍历方式都可以

但是!具体问题要具体分析,这里说的仅仅是纯背包问题的遍历顺序

顺便把例题做了吧,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func main() {
weight := []int{1, 3, 4}
value := []int{15, 20, 30}
bagWeight := 4
// 因为容量包含0,所以要+1
dp := make([]int, bagWeight+1)
// 遍历物品
for i := 0; i < len(weight); i++ {
// 遍历容量
for j := weight[i]; j <= bagWeight; j++ {
dp[j] = max(dp[j], dp[j-weight[i]]+value[i])
}
}
fmt.Println(dp)
}

零钱兑换 II

题目链接

给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0

假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带符号整数。

示例 1:

1
2
3
4
5
6
7
输入: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:

1
2
3
输入:amount = 3, coins = [2]
输出:0
解释:只用面额 2 的硬币不能凑成总金额 3 。

示例 3:

1
2
输入:amount = 10, coins = [10] 
输出:1

提示:

  • 1 <= coins.length <= 300
  • 1 <= coins[i] <= 5000
  • coins 中的所有值 互不相同
  • 0 <= amount <= 5000

代码

和01背包中的那个题一样,组合问题:dp[j] += dp[j - nums[i]],没啥好解释的

1
2
3
4
5
6
7
8
9
10
func change(amount int, coins []int) int {
dp := make([]int, amount+1) //总金额为i时,有dp[i]种兑换方法
dp[0] = 1
for i := 0; i < len(coins); i++ {
for j := coins[i]; j <= amount; j++ {
dp[j] += dp[j-coins[i]]
}
}
return dp[amount]
}

遍历顺序分析

但是注意,这里遍历顺序必须时先物品后容量!

因为纯完全背包求得装满背包的最大价值是多少,和凑成总和的元素有没有顺序没关系,即:有顺序也行,没有顺序也行!而本题要求凑成总和的组合数,元素之间明确要求没有顺序。所以纯完全背包是能凑成总和就行,不用管怎么凑的。本题是求凑出来的方案个数,且每个方案个数是为组合数。

外层for循环遍历物品(钱币),内层for遍历背包(金钱总额)的情况,得到的方法数量只有{1, 5}这种情况。而不会出现{5, 1}的情况。

如果把两个for交换顺序,背包容量的每一个值,都是经过 1 和 5 的计算,包含了{1, 5} 和 {5, 1}两种情况。此时dp[j]里算出来的就是排列数!

总结

  • 如果求组合数就是外层for循环遍历物品,内层for遍历背包
  • 如果求排列数就是外层for遍历背包,内层for循环遍历物品

组合总和 Ⅳ

题目链接

给你一个由 不同 整数组成的数组 nums ,和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

进阶:如果给定的数组中含有负数会发生什么?问题会产生何种变化?如果允许负数出现,需要向题目中添加哪些限制条件?

示例 1:

1
2
3
4
5
6
7
8
9
10
11
12
输入: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:

1
2
输入:nums = [9], target = 3
输出:0

提示:

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 1000
  • nums 中的所有元素 互不相同
  • 1 <= target <= 1000

分析

标题写的时组合,实际上时排序,没啥好说的,for循环调换一下,换的时候注意需要把j-nums[i]<0的部刨掉

  • 如果求组合数就是外层for循环遍历物品,内层for遍历背包
  • 如果求排列数就是外层for遍历背包,内层for循环遍历物品

进阶:如果给定的数组中含有负数,则会导致出现无限长度的排列。
例如:有个-5,有个3。那我选3个-5,再选5个3,它们的和为0,那就抵消了,按照倍数往上加,像6个-5、10个3也是0,这样成倍增长下去,那就没完了

代码

1
2
3
4
5
6
7
8
9
10
11
12
func combinationSum4(nums []int, target int) int {
dp := make([]int, target+1)
dp[0] = 1
for j := 0; j <= target; j++ {
for i := 0; i < len(nums); i++ {
if j-nums[i] >= 0 { // 这个判断得单独处理
dp[j] += dp[j-nums[i]]
}
}
}
return dp[target]
}

爬楼梯进阶版

假设你正在爬楼梯。需要 n 阶你才能到达楼顶,你每次可以上1至m个台阶,n、m均为输入。你有多少种不同的方法可以爬到楼顶呢?

分析

  • 每一阶可以重复使用,例如跳了1阶,还可以继续跳1阶——完全背包
  • 跳到楼顶有几种方法——排序问题

从而确定遍历顺序:

  • 完全背包:容量正序遍历
  • 排序问题:先容量再物品

dp[i]:爬到有i个台阶的楼顶,有dp[i]种方法。递推公式:dp[i] += dp[i - j]。初始化:dp[0]=0

代码

1
2
3
4
5
6
7
8
9
10
func climbStairs(n int,m int) int {
dp := make([]int,n+1)
dp[0] = 1
for j := 0; j <= n; j++ {
for i := 0; i < m; i++ {
dp[j] += dp[j-i]
}
}
return dp[n]
}

零钱兑换

给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1

你可以认为每种硬币的数量是无限的。

示例 1:

1
2
3
输入:coins = [1, 2, 5], amount = 11
输出:3
解释:11 = 5 + 5 + 1

示例 2:

1
2
输入:coins = [2], amount = 3
输出:-1

示例 3:

1
2
输入:coins = [1], amount = 0
输出:0

提示:

  • 1 <= coins.length <= 12
  • 1 <= coins[i] <= 2^31 - 1
  • 0 <= amount <= 10^4

分析

  • 确定dp数组:凑足总额为j所需钱币的最少个数为dp[j]
  • 确定递推公式:dp[j] = min(dp[j - coins[i]] + 1, dp[j])
  • dp数组如何初始化[值得注意]:非0的元素都是应该是最大值,dp[0]=0
  • 遍历顺序:求钱币最小个数,那么钱币有顺序和没有顺序都可以,都不影响钱币的最小个数

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
func coinChange(coins []int, amount int) int {
dp := make([]int, amount+1) // 总金额为i时,最少硬币数为dp[i]
// dp[j] = min(dp[j],dp[j-coins[i]]+1)
for i := 1; i <= amount; i++ {
dp[i] = math.MaxInt32
}
for i := 0; i <= len(coins); i++ {
for j := coins[i]; j <= amount; j++ {
dp[j] = min(dp[j], dp[j-coins[i]]+1)
}
}
return dp[amount]
}

完全平方数

给你一个整数 n ,返回 和为 n 的完全平方数的最少数量

完全平方数 是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,14916 都是完全平方数,而 311 不是。

示例 1:

1
2
3
输入:n = 12
输出:3
解释:12 = 4 + 4 + 4

示例 2:

1
2
3
输入:n = 13
输出:2
解释:13 = 4 + 9

提示:

  • 1 <= n <= 10^4

分析

题目翻译:完全平方数就是物品(可以无限件使用),凑个正整数n就是背包,问凑满这个背包最少有多少物品

  • 完全背包
  • 遍历顺序没要求

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func numSquares(n int) int {
dp := make([]int, n+1) // j需要的最少平方数个数
for i := 1; i <= n; i++ {
dp[i] = math.MaxInt32
}
m := int(math.Pow(float64(n), 0.5))
// 遍历物品
for i := 0; i <= m; i++ {
// 遍历容量
for j := i * i; j <= n; j++ {
dp[j] = min(dp[j], dp[j-i*i]+1)
}
}
return dp[n]
}

多重背包

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

多重背包和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背包问题了,且每个物品只用一次。

所以可以直接把它看成01背包来做。当然另一种实现方式,就是把每种商品遍历的个数放在01背包里面在遍历一遍。即01背包里面在加一个for循环遍历一个每种商品的数量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 多重背包可以化解为 01 背包
func multiplePack(weight, value, nums []int, bagWeight int) int {

for i := 0; i < len(nums); i++ {
for nums[i] > 1 {
weight = append(weight, weight[i])
value = append(value, value[i])
nums[i]--
}
}

res := make([]int, bagWeight+1)
for i := 0; i < len(weight); i++ {
for j := bagWeight; j >= weight[i]; j-- {
res[j] = getMax(res[j], res[j-weight[i]]+value[i])
}
}

return res[bagWeight]
}

背包总结

01背包:

  • 物品只能用一次
  • 二维数组时,遍历顺序均可
  • 一维数组只能先物品后容量,容量倒序遍历

完全背包:

  • 物品可用无限次
  • 容量正序遍历(保证无限次)
  • 一维数组遍历顺序均可,常见特例如下:
    • 组合数:先遍历物品,再遍历容量(背包)
    • 排序数:先遍历容量(背包),再遍历物品

多重背包:转换成01背包来做

组合、排序问题递推通常公式为:dp[i] += dp[i - j],初始化dp[0]=0

OK,你已经掌握01背包、完全背包、多重背包了,快去solo面试官吧!

 评论
评论插件加载失败
正在加载评论插件