01背包
动规入门:0/1背包
前言
0/1 背包问题,作为动态规划问题的经典问题,可以帮助捋顺思维。之所以叫0/1背包,是因为在这类问题中每种物品只有一个,每个物品只有放和不放两种选择,即对于一种物品,可以表示为0和1两种状态。因此0/1背包统计的是 恒定容量 储存数个 不同物品 的 最大价值。核心在于确认好初始状态、递推基数和递推增量(反正就是
dp[i][j-?] + ?
,理解万岁)。说白了主要难点还是在确认递推关系上。
一、经典0/1背包问题
有 n(n ≤ 100) 个物品和一个容量为 m(m ≤ 10000) 的背包。
第 i 个物品的容量是 c[i],价值是 w[i]。现在需要选择一些物品放入背包,并且总容量不能超过背包容量,求能够达到的物品的最大总价值。
1、状态设计
动态规划的最核心之一是确认好dp数组的含义。这决定了你接下来的递推关系和最终问题的返回值。(不知道为什么叫dp数组的自己去查动态规划的英文)每次当你找递推关系出现问题的时候,最好的方法就是回头看一下你确认的dp数组的含义。如果实在找不出,那就要考虑是否在这最开始就出现了问题。
在01背包问题中,我们一般情况下这么设定dp数组:
根据题目要求,我们很容易想到用一对数(i, j)
表示前 i
个物品恰好放入容量为 j
的背包 (0 ≤ i < n,0 ≤ j ≤ m)
;
因此我们的数组 dp[i][j]
表示状态 (i, j)
下该背包得到的最大价值,即前 i
个物品恰好放入容量为 j
的背包所得到的最大总价值;
2、状态转移方程
列出状态转移方程如下:
假设前i-1
个物品已经统计完毕,现在正在统计第i
个物品的情况。因为每个物品要么放,要么不放,所以只需要考虑两种情况:
1)不放:如果 “第 i 个物品不放入容量为 j 的背包”,那么问题转化成求 “前 i-1 个物品放入容量为 j 的背包” 的问题;由于不放,所以最大价值就等于 “前 i-1 个物品放入容量为 j 的背包” 的最大价值,即 dp[i-1][j]
;
2)放:如果 “第 i 个物品放入容量为 j 的背包”,那么问题转化成求 “前 i-1 个物品放入容量为 j-c[i] 的背包” 的问题;那么此时最大价值就等于 “前 i-1 个物品放入容量为 j-c[i] 的背包” 的最大价值,加上放入第 i 个物品的价值,即 dp[i-1][j - c[i]] + w[i]
将以上两种情况取大者,就是我们所求的 “前 i 个物品恰好放入容量为 j 的背包” 的最大价值了。
我知道可能有点绕,这种时候就要请你回去看一下上面状态设计里的内容了。
3、初始状态
既然使用递推关系解决问题,初始状态的正误直接影响了整个问题的正误。
在这个01背包问题中,我们发现,当状态在进行转移的时候,(i, j)
不是来自 (i-1, j)
,就是来自 (i-1, j - c[i])
,所以必然有一个初始状态,而这个初始状态就是 (0, 0)
,含义是 “前 0 个物品放入一个背包容量为 0 的背包”,这个状态下的最大价值为 0
,即 dp[0][0] = 0
;后续的状态都可以由它递推得出,你可以手动推一下试试就明白了。
我知道可能有点绕,这种时候就要请你回去看一下上面状态设计里的内容了。(梅开二度)
4、非法状态
那么我们再来考虑,如果出现了 (0, 3) ,这是什么意思呢?它代表的是 “前 0 个物品恰好放入一个背包容量为 3 的背包”,明显这种情况是不存在的,因为 0 个物品的价值肯定是 0。所以这种状态被称为非法状态,非法状态是无法进行状态转移的。我们需要对他们也进行初始化。
我知道可能有点绕,这种时候就要请你回去看一下上面状态设计里的内容了。(帽子戏法)
5、状态初始化
其中 x
在程序实现时,我们可以设定一个非常小的数,比如 -1000000000
,只要保证无论如何状态转移它都不能成为最优解的候选状态即可。
二、练习
变形题:416. 分割等和子集 - 力扣(LeetCode)
给你一个 只包含正整数 的 非空 数组
nums
。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。
分析
这道题可以换一种表述:给定一个只包含正整数的非空数组nums[]
,判断是否可以从数组中选出一些数字,使得这些数字的和等于整个数组的元素和的一半。这个问题可以转换成「01 背包问题」。
与传统的「01 背包问题」的区别在于,传统的「01 背包问题」要求选取的物品的重量之和不能超过背包的总容量,这道题则要求选取的数字的和恰好等于整个数组的元素和的一半。类似于传统的「01 背包问题」,可以使用动态规划求解。
在使用动态规划求解之前,首先需要根据数组的长度 n
判断数组是否可以被划分。如果 n<2
,则不可能将数组分割成元素和相等的两个子集,因此直接返回 false
。其次判断数组元素的和是不是奇数,此时也不可能平分。
由于我们的目的是得知目标是否存在,因此dp数组记录的应该是对于前i
个物品,能否组合出和为sum
的结果。可以为1,不可以则为0。此时的初始情况如下:
-
如果不选取任何正整数,则被选取的正整数等于 0。因此对于所有
0≤i<n
,都有dp[i][0]=true
。 -
当
i==0
时,只有一个正整数nums[0]
可以被选取,因此dp[0][nums[0]]=true
。
状态转移方程为:
这里出现了一个位运算符或|
,不需要我搓个表格告诉你他的作用吧?
想想为什么是这样?(你知道我要说什么.jpg)
根据dp数组的定义,我们可以得知dp[numsSize-1][sum/2]
的存在与否就是我们要求的解。
源码
1 | bool canPartition(int* nums, int numsSize){ |
1262. 可被三整除的最大和 - 力扣(LeetCode)
自己动脑筋吧~(提示一下,同余理论很好用哦!)
要是真的不会,你已经是一个成熟的CSer了,要学会自己寻找答案哦~
本蒟蒻の代码如下:
1 | int maxSumDivThree(int* nums, int numsSize) { |