盗窃存在最优算法吗？
假如法外狂徒张三，这次犯的是入室盗窃罪，咱先不着急判张三的（张三：丫的天天判我..），这次咱先让张三好好偷着爽一把...
问题背景：
月黑风高的夜晚，法外狂徒张三开启了法外狂徒模式。他背着一个可装载重量为 W 的背包，地主家有 N 个物品，每个物品有重量和价值两个属性。
其中第 i 个物品的重量为 wt[i]，价值为 val[i]，问张三现在用这个背包装物品，最多能装的价值是多少？
举例：
N = 3 //地主家有三样东西
wt = [2,1,3] //每样东西的重量
val = [4,2,3] //每样东西的价值
W = 4 //背包可装载重量
算法应该返回6.
因为：选择第一件物品和第二件物品，在重量没有超出背包容量下，所选价值最大。
如果每种物品只能选 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]]时的价值
上述两个如果可以表述成以下if判断代码：
//如果第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
我们首先初始化一行和一列 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
现在我们走到了当背包容量 W = 2 的时候，此时当前 i (依旧第一个物品)能否装进背包里呢？
我们发现 4 > 2，此时还是装不进去，那么同样继承上一个结果。
上一个结果是 i 不变(依旧是第 0 个物品),W = 2，所以结果依旧为 0。
现在来到 W = 3，发现依旧装不进去，所以填 0。
下一步到 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
下一步我们来到 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 数组：
(为啥前边图那么漂亮这个这么。因为前边我是在一个背包问题的交互式 web 界面操作的，数据是随机的，结果不小心刷新了下网页，数据被刷新找不回来了，无奈最后自己在 pad 上画了(丑)表，自己手算了遍[捂脸])。
交互式 web 操作地址：https://alchemist-al.com/algorithms/knapsack-problem
最后的dp[4] [6]：考虑前四个物品，背包容量为 6 的情况下，可装入的最大价值，即为所求
(注意：我们在这里求的是 0-1 背包问题，即某一个物品只能选择 0 个或 1 个，不能多选！有些小伙伴看到最后答案 14 可不要犯糊涂。)
请读者再反复理解上述图表内容(即：状态转移方程)
代码
那么我们根据上述表述，很容易的就可以写出代码：
两层 for 循环
1.外层循环 i 遍历物品(即前几个物品)：
for(inti=1;i<=N;i++){
...
}
2.内层循环 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 上并没有这个原题，所以对于背包问题，最重要的是它的变种。
背包问题是一大类问题的统称，很大一部分动态规划的题深层剖析都可以转换为背包问题。
所以大家还需要理解体会背包问题的核心思想，再将此种思想运用到其它一类背包问题的问题上。
那么背包问题还有哪些变化呢？我们下期再说
