经典动态规划:0-1 背包问题

时间:2021-05-02

问题背景

月黑风高的夜晚,张三开启了法外狂徒模式:他背着一个可装载重量为 W 的背包去地主家偷东西。

地主家有 N 个物品,每个物品有重量和价值两个属性,其中第 i 个物品的重量为 wt[i],价值为 val[i]。

问张三现在用这个背包装物品,最多能装的价值是多少?

举例:

  • N = 3 //地主家有三样东西
  • wt = [2,1,3] //每样东西的重量
  • val = [4,2,3] //每样东西的价值
  • W = 4 //背包可装载重量

算法应该返回 6.

因为选择第一件物品和第二件物品,在重量没有超出背包容量下,所选价值最大。

如果每种物品只能选 0 个或 1 个(即要么将此物品装进包里要么不装),则此问题称为 0-1 背包问题;如果不限每种物品的数量,则称为无界(或完全)背包问题。

今天这篇文章我们只关注 0-1 背包问题,下一篇文章再聊完全背包问题。

那我们是如何选择要装入的物品的?

思路初探

首先,质量很大价值很小的物品我们先不考虑(放着地主家金银财宝珍珠首饰不偷,背出来一包煤...,那也就基本告别盗窃行业了...)

然后呢?再考虑质量大价值也大的?还是质量较小价值也稍小的?

我们自然而然想到:装价值/质量 比值最大的,因为这至少能说明,此物品的“价质比”最大(也即贪心算法,每次选择当前最优)

那么这样装能保证最后装入背包里的价值最优吗?

我们先来看一个例子:

假设有 5 个物品,N = 5,每种物品的质量与价值如下:

  • W : 20, 30, 40, 50, 60
  • V : 20, 30, 44, 55, 60
  • V/W: 1, 1, 1.1, 1.1, 1

背包容量为 100

如果按上述策略:优先选“价质比”最大的:即第三个和第四个物品

  • 此时质量:40+50=90
  • 价值:44+55 =99

但我们知道,此题更优的选择策略是:选第一个,第二个和第四个

  • 此时质量:20+30+50=100
  • 价值:20+30+55=105

所以,我们的“价质比”这种贪心策略显然不是最优策略。

读过一文学懂动态规划这篇文章的读者会发现,之前文章中兑换零钱例子我们最开始也是采取贪心策略,但最后发现贪心不是最优解,由此我们引出了动态规划。

没错,今天这题也正是动态规划又一经典的应用。

解题思路

根据动之前的文章我们知道,动态规划的核心即:状态与状态转移方程。

那么此题的状态是什么呢?

状态

何为状态?

说白了,状态就是已知条件。

重读题意我们发现:此题的已知条件只有两个:

  • 背包容量
  • 可选的物品

题目要求的是在满足背包容量前提下,可装入的最大价值。

那么我们可以根据上述状态定义出 dp 数组,即:

dp[i][w] 表示:对于前i个物品,当前背包的容量为w,这种情况下可以装的最大价值是dp[i][w]

我们自然而然的考虑到如下特殊情况:

当 i = 0 或 w = 0,那么:

dp[0][...] = dp[...][0] = 0

解释:

对前 0 个物品而言,无论背包容量等于多少,装入的价值为 0;

当背包容量为 0 时,无论装入前多少个物品(因为一个都装不进去),背包里的价值依旧为 0。

根据这个定义,我们求的最终答案就是dp[N][W]

我们现在找出了状态,并找到了 base case,那么状态之间该如何转移呢(状态转移方程)?

状态转移方程

dp[i][w] 表示:对于前i个物品,当前背包的容量为w,这种情况下可以装的最大价值是dp[i][w]。

思考:对于当前第 i 个物品:

  • 如果没有把第 i 个物品装入包里(第 i 个物品质量大于当前背包容量):那么很显然,最大价值dp[i][w]应该等于dp[i - 1][w],没有装进去嘛,故当前背包总价值就等于之前的结果,即第i - 1 个物品之前的总价值 。
  • 如果把第 i 个物品装入了包里,那么 dp[i][w]应该等于什么呢?

它应该等于下面两者里的较大值:

  • dp[i - 1][w] //前i - 1个物品,背包所装的最大价值
  • dp[i - 1]w - wt[i]] + val [i] //当前第 i 个物品我装里边了,那么此时背包装入的总价值即为:当前第 i 个物品的价值 val [i] + 第 i 个物品之前,背包容量为w - wt[i](w 减去当前第 i 个物品的质量)dp[i - 1]w - wt[i]] 时的价值
  • 上述两个如果可以写成以下代码:

  • //如果第i个物品质量大于当前背包容量
  • if(wt[i]>W){
  • dp[i][W]=dp[i-1][W];//继承上一个结果
  • }else{
  • //在“上一个结果价值”和“把当前第i个物品装入背包里所得到价值”二者里选价值较大的
  • dp[i][W]=Math.max(dp[i-1][W],dp[i-1][W-wt[i]]+val[i])
  • }
  • 例子

    我们接来下再用一个具体的例子,来理解状态和状态转移方程。

    现在我们有 4 个物品,物品对应的价值与质量分别如上图左侧所示:

    • 6, 4
    • 2,5
    • 1, 4
    • 8, 1

    Step 1

    我们首先初始化一行和一列 0,分别对应dp[0][w] 和 dp[i][0]。

    那么第一个问号处应该填什么呢?

    我们根据上述表述的状态转移关系来判断:

    当前第一个物品的重量 4 > 背包容量,故装不进去,所以继承上一个结果。

    上一个结果是什么呢?

    就是第 i - 1个物品,也就是第 0 个,和W = 1时的价值:

  • if(wt[i]>W){
  • dp[i][W]=dp[i-1][W];//继承上一个结果
  • }
  • 此时方框里的值为 0,故第一个问号这里应该填 0

    Step 2

    现在我们走到了当背包容量 W = 2 的时候,此时当前 i (依旧第一个物品)能否装进背包里呢?

    我们发现 4 > 2,此时还是装不进去,那么同样继承上一个结果。

    上一个结果是 i 不变(依旧是第 **0 **个物品),W = 2,所以结果依旧为 0。

    Step 3

    现在来到 W = 3,发现依旧装不进去,所以填 0。

    Step 4

    下一步到 W = 4 这里了,

    此时物品重量 4 = 4(背包容量),可以装里,那么按照之前状态转移关系应该是:

  • else{
  • //在“上一个结果价值”和“把当前第i个物品装入背包里所得到价值”二者里选价值较大的
  • dp[i][W]=Math.max(dp[i-1][W],dp[i-1][W-wt[i]]+val[i])
  • }
  • Option A:

    • 上一个结果 : dp[i - 1][w],即dp[0][4] = 0

    Option B:

    • 把当前第 i 个物品装入背包里所得到价值:dp[i - 1]W - wt[i]] + val [i]

    此时第一个物品的重量为 4,背包容量为 4,

    故要想装入重量为 4 的此物品,那么背包先前的容量必须为当前背包容量 - 当前物品容量:4 - 4 = 0。

    我们随即找到在没装入此物品(重量为 4,价值为 6)之前的dp[i -1]W - wt[i]] = dp[0][0] = 0

    那么dp[i -1]W - wt[i]] + val [i] = 0 + 6 = 6

    6 和 0 选择一个最大值,所以这里问号处应填入6

    Step 5

    下一步我们来到 W = 5 这里,此时依旧是第一个物品,质量 4 < 5(背包容量),我们可以装里边。

    然后我们在

    Option A:

    • 上一个结果 :dp[0][5] = 0

    Option B:

    • 把当前第 i 个物品装入背包里所得到价值:dp[i -1]W - wt[i]] + val [i]

    此时第一个物品的重量为 4,背包容量为 5

    故要想装入重量为 4 的此物品,那么背包先前的容量必须为:当前背包容量 - 当前物品容量:5 - 4 = 1 ,

    我们随即找到在没装入此物品(重量为 4,价值为 6)之前的dp[i - 1]W - wt[i]] = dp[0][1] = 0

    那么dp[i -1]W - wt[i]] + val [i] = 0 + 6 = 6

    选择一个最大值,即 6,所以此处应该填入 6

    我们根据以上状态转系关系,依次可以填出空格其它值,最后我们得到整个 dp 数组:

    V W 0 1 2 3 4 5 6 0 0 0 0 0 0 0 0 0 6 4 0 0 0 0 6 6 6 2 5 0 0 0 0 6 6 6 1 4 0 0 0 0 6 6 6 8 1 0 8 8 8 8 14 14

    最后的 dp[4][6]:考虑前四个物品,背包容量为 6 的情况下,可装入的最大价值,即为所求。

    (注意:我们在这里求的是 0-1 背包问题,即某一个物品只能选择 0 个或 1 个,不能多选!)

    代码

    根据以上思路,我们很容易写出代码:

    两层 for 循环

    外层循环 i 遍历物品(即前几个物品):

  • for(inti=1;i<=N;i++){
  • ...
  • }
  • 内层循环 j 遍历 1~W(背包容量)之间的整数值:

    然后写入状态转移方程

  • for(intj=0;j<=W;j++){
  • //外层循环i,如果第i个物品质量大于当前背包容量
  • if(wt[i]>W){
  • dp[i][W]=dp[i-1][W];//继承上一个结果
  • }else{
  • //在“上一个结果价值”和“把当前第i个物品装入背包里所得到价值”二者里选价值较大的
  • dp[i][W]=Math.max(dp[i-1][W],dp[i-1][W-wt[i]]+val[i])
  • }
  • }
  • 由此我们给出完整代码:

  • classsolution{
  • publicintknapsackProblem(int[]wt,int[]val,intsize){
  • //定义dp数组
  • int[][]dp=newint[wt.length][size];
  • //对于装入前0个物品而言,dp数组储存的总价值初始化为0
  • for(inti=0;i<size;i++){
  • int[0][i]=0;
  • }
  • //对于背包容量W=0时,装入背包的总价值初始化为0
  • for(intj=0;j<size;j++){
  • int[j][0]=0;
  • }
  • //外层循环遍历物品
  • for(inti=1;i<=N;i++){
  • //内层循环遍历1~W(背包容量)
  • for(intj=0;j<=W;j++){
  • //外层循环i,如果第i个物品质量大于当前背包容量
  • if(wt[i]>W){
  • dp[i][W]=dp[i-1][W];//继承上一个结果
  • }else{
  • //在“上一个结果价值”和“把当前第i个物品装入背包里所得到价值”二者里选价值较大的
  • dp[i][W]=Math.max(dp[i-1][W],dp[i-1][W-wt[i]]+val[i])
  • }
  • }
  • }
  • }
  • }
  • 只要我们定义好了状态(dp 数组的定义),理清了状态之间是如何转移的,最后的代码水到渠成。

    本文所说的这个 0-1 背包问题,Leetcode 上并没有这个原题,所以对于背包问题,最重要的是它的变种。

    背包问题是一大类问题的统称,很大一部分动态规划的题深层剖析都可以转换为背包问题。

    所以还需要理解体会背包问题的核心思想,再将此种思想运用到其它一类背包问题的问题上。

    那么背包问题还有哪些变化呢?我们下期见~

    原文地址:https://mp.weixin.qq.com/s/a4w3MmAJzK0TFL_E3Kwbow

    声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。

    相关文章