动态规划和贪心算法之背包问题理解

た入场券 2021-09-11 01:14 523阅读 1赞

## [漫画：什么是动态规划？][Link 1]   [LeetCode : 518. Coin Change 2凑硬币][LeetCode _ 518. Coin Change 2]   **一.背包问题** ##

引用书上关于0-1背包和部分背包的阐述：  
![这里写图片描述][20160817212952924]  
![这里写图片描述][20160817213007346]

## **二.贪心与动态规划区别** ##

关于红色矩形部分解释为什么0-1不能使用贪心算法，是因为当你选择一个物品时，整个物品的大小都需要计算，然而背包的的大小又是固定的，那么剩下的背包大小与剩下的物品之间就有个容纳问题。就像图b第二个树状图属于容量20，而剩余物品大小30，显然放不下，所以说选择放与不放会影响后放物体能否尽可能填满背包。这个与部分背包问题不同，部分背包问题，只要选择从价值高到低放就能够铁定填满，它的填放会影响价值，但是不会影响背包能否填满。  
可以把0-1背包想成往一个杯子里放几种固定大小铁块（但是没有极其小可以用来填补空缺的）。  
可以把部分背包想成往一个杯子里放粉末。先放石子，再放沙，最后水。

## **三.0-1背包动态规划问题** ##

部分背包很好理解，接下来说一说关于0-1背包问题。在参考别人答案后，我想了好多关于遇到这种问题，我们该以何种顺序，如果抓住问题解题关键点。

> 例子：5个物品，（重量w，价值v）分别为：（5，12），（4，3），（7，10），（2，3），（6，6）。

**1、假设问题答案**  
　　我们共有5个物品，答案可以是（1表示取，0表示弃）：00011或者10101或者11000等等。不过不要用1，2，3，4，5代表物品，再用15或者123或者345表示答案。你会发现如果你只考虑取的部分不考虑弃的部分 ，问题答案位数一直不是固定的，增加难度。  
**２、假设最优答案**  
　　我们假设最优答案为00011。这样根据动态规划要求，考虑最优子问题。一般考虑子问题都是减少问题包含元素数量，同时保持子问题与原问题属于同种问题，只是考虑数量减少了。比如我们减少第五个背包。那我们的问题变成了什么？这里考虑极其特殊情况，除去的是最后一个物品。

> 例子：4个物品，（重量w，价值v）分别为：（5，12），（4，3），（7，10），（2，3）。

**3、找到原问题与子问题之间联系**  
　　当00011为原问题最优解，那么0001为子问题最优解。为啥？如果0001不是子问题最优解，假设0101为子问题最优解，那原问题最优解就是01011或者01010。与我们假设相悖。  
　　那么从子问题到原问题要经过什么样考虑？我们现在已经找到子问题最优解，到原问题解我们只需考虑第五个物品是取还是弃？如果取，那么取以后背包空余量减少，背包价值增大；如果弃，背包价值也会变化，因为此时我们背包容量变大了，那么我们先前的取法就有可能需要改变。所以我们需要在这里进行判断。  
　　如果一个问题的最优解包含了物品n，即物(n)=1，那么其余物1，物2，…，物(n-1)一定构成子问题1，2，…，n-1在背包容量W-w(n)时的最优解。如果这个最优解不包含物品n，即物n=0，那么其余物1，物2，…，物(n-1)一定构成子问题1，2，…，n-1在背包容量W时的最优解。  
**4、迭代公式的建立**  
　　首先我们需要考虑是什么可以让我们把问题拆分成子问题？在矩阵链中我们是根据矩阵链中拥有的矩阵Ａ个数来拆分的。通过缩小矩阵个数变成子问题。那么在0-1背包中是否也可以减少个数呢？答案是不一定。假设我们现在考虑选取两个物品，我们是可以直接选择两个价值和最大物品。但是还有一个因素：重量和问题。在重量和不等情况下认为价值和最大的两个物品总价值最大。显然这是不公平的。所以这里我们需要考虑两个因素：一个是物品数量，另一个是背包容量  
　　再考虑一下我们问题的变量有哪些？这个地方考虑的只是变量变化的一个相对关系。  
　　背包物品i 　　背包当前拥有价值tab 　　背包当前重量j  
0 　　　　　　　0　　　　　　　　　　 0  
1　　　　　　　 12　　　　　　　　　　5  
2 　　　　　　　12+3=15 　　　　　　5+4=9  
…  
可以看到我们添加一个物品，背包价值增加，背包重量增加。  
根据步骤3中我们可以发现：  
　tab(i+1) = max( tab(i) + v(i+1) , tab(i) )  
　j(i+1) = j(i) + w(i+1) 或者 j(i) 此处变化跟上一个公式对应。  
目前的话我们有两个变化公式，在迭代中我们将其转化成一个：

**tab\[i\]\[j\] = max(tab\[i-1\]\[j-weight\[i\]\]+value\[i\],tab\[i-1\]\[j\]) (\{i,j|0< i <=n,0<= j <=total\})**

**5、例题解析过程**  
　　到第4步，我们已经完成问题的思考，接下来看一下，例题的思考过程，加深理解。  
![这里写图片描述][20160819234933071]  
　　看图片中表格第一行，我们就是通过控制背包容量来控制子问题大小。随着背包容量增加，能够容纳更多物品，逐渐扩大，最后直至达到问题背包容量。  
　　当i=1时，只能选一个1物品，看1物品行（表中第六行），随着背包容量增大，背包可以放得下1物品  
　　当i=2时，可以选1物品和2物品，当背包容量增大至4时，此时我们可以选择2物品价值为3；继续增大背包容量，当背包容量增大至5时，我们可以不放2物品放1物品，价值为12；当背包容量为9时，1物品2物品都可以放得下，两个都放，价值15。  
　　。。。。。。  
　　看下迭代公式：  
　　**tab\[i\]\[j\] = max(tab\[i-1\]\[j-weight\[i\]\]+value\[i\],tab\[i-1\]\[j\]) (\{i,j|0< i <=n,0<= j <=total\})**  
　　当决定是否放入i时，我们需要考虑两种子问题。  
　　一：如果放入，那我们考虑在物品数为i-1， 背包容量为j-weight\[i\]时的价值  
　　二：如果不放入，物品数为i-1， 重量为j时的价值  
　　哪一个大，选择哪一个。

**迭代公式寻找规律**  
1、确定在当前迭代次数下有多少种可能结果，是需要保存最优还是多种都要保存，一般决定了是使用一维还是二维数组存放。  
2、确定每种情况往前一次推导需要遍历哪些情况，也就是新加一个元素后可能有情况哪些产生。  
3、 确定迭代初始点，迭代次数。

[Link 1]: https://zhuanlan.zhihu.com/p/31628866
[LeetCode _ 518. Coin Change 2]: https://blog.csdn.net/qq_16234613/article/details/92850953
[20160817212952924]: /images/20210520/6456c275fbaf43bd8f8a517c9450067f.png
[20160817213007346]: /images/20210520/859e8400785141e185b9075e843b19c0.png
[20160819234933071]: /images/20210520/2d3b6b26f26646ca899c35f58f0e7374.png