前言

通过后面三篇动静布局文章的介绍，置信大家对动静布局、分治、贪婪有了充沛的了解，对动静布局的 3 个外围问题、其本质也有了理解。

纸上得来终觉浅，绝知此事要躬行。

那么明天开始咱们来聊聊具体的那些面试时常考的题目。

（还没有看过前三篇文章的同学齐姐叫你补课啦～）

（一）：初识动静布局

（二）：动静布局的 3 个外围问题

（三）：动静布局的实质

问题背景

月黑风高的夜晚，张三开启了法外狂徒模式：他背着一个可装载重量为 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，那么：

dp0 = dp... = 0

解释：
对前 0 个物品而言，无论背包容量等于多少，装入的价值为 0；

当背包容量为 0 时，无论装入前多少个物品（因为一个都装不进去），背包里的价值仍旧为 0。

依据这个定义，咱们求的最终答案就是dp[N][W]

咱们当初找出了状态，并找到了 base case，那么状态之间该如何转移呢（状态转移方程）？

状态转移方程

dpi 示意：对于前i个物品，以后背包的容量为w，这种状况下能够装的最大价值是dp[i][w]。

思考：对于以后第 i 个物品：

  • 如果没有把第 i 个物品装入包里（第 i 个物品品质大于以后背包容量）：那么很显然，最大价值dpi应该等于dpi - 1，没有装进去嘛，故以后背包总价值就等于之前的后果，即第i - 1 个物品之前的总价值 。
  • 如果把第 i 个物品装入了包里，那么 dpi应该等于什么呢？

它应该等于上面两者里的较大值：

  1. dpi - 1 //前i - 1个物品，背包所装的最大价值
  2. 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，别离对应dp0 和 dpi。

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

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

以后第一个物品的分量 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:

  • 上一个后果 : dpi - 1，即dp0 = 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]] = dp0 = 0

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

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

Step 5

下一步咱们来到 W = 5 这里，此时仍旧是第一个物品，品质 4 < 5(背包容量)，咱们能够装里边。

而后咱们在

Option A:

  • 上一个后果 ：dp0 = 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]] = dp0 = 0

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

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

咱们依据以上状态转系关系，顺次能够填出空格其它值，最初咱们失去整个 dp 数组：

VW0123456
000000000
640000666
250000666
140000666
81088881414

最初的 dp4：思考前四个物品，背包容量为 6 的状况下，可装入的最大价值，即为所求。

(留神：咱们在这里求的是 0-1 背包问题，即某一个物品只能抉择 0 个或 1 个，不能多选！)

代码

依据以上思路，咱们很容易写出代码：

两层 for 循环

  1. 外层循环 i 遍历物品(即前几个物品)：
for(int i = 1;i <=N;i++){        ...}
  1. 内层循环 j 遍历 1~W(背包容量)之间的整数值：

而后写入状态转移方程

for(int j = 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])    }}

由此咱们给出残缺代码：

class solution{        public int knapsackProblem(int[] wt,int[] val,int size){                //定义dp数组                int[][] dp = new int[wt.length][size];                //对于装入前0个物品而言，dp数组贮存的总价值初始化为0                for(int i = 0;i < size;i++){                    int[0][i] = 0;                }                //对于背包容量W=0时，装入背包的总价值初始化为0                for(int j = 0;j < size;j++){                    int[j][0] = 0;                }                //外层循环遍历物品                for(int i = 1;i <= N;i++){                    //内层循环遍历1~W(背包容量)                    for(int j = 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 上并没有这个原题，所以对于背包问题，最重要的是它的变种。

背包问题是一大类问题的统称，很大一部分动静布局的题深层分析都能够转换为背包问题。

所以还须要了解领会背包问题的核心思想，再将此种思维使用到其它一类背包问题的问题上。

那么背包问题还有哪些变动呢？咱们下期见～