阅读之前看这里👉:博主是一名正在学习数据类知识的学生,在每个领域我们都应当是学生的心态,也不应该拥有身份标签来限制自己学习的范围,所以博客记录的是在学习过程中一些总结,也希望和大家一起进步,在记录之时,未免存在很多疏漏和不全,如有问题,还请私聊博主指正。
博客地址:天阑之蓝的博客,学习过程中不免有困难和迷茫,希望大家都能在这学习的过程中肯定自己,超越自己,最终创造自己。
【数据结构与算法知识】—动态规划之01背包问题
题目: 给定 n 件物品,物品的重量为 w[i],物品的价值为 c[i]。现挑选物品放入背包中,假定背包能承受的最大重量为V,问应该如何选择装入背包中的物品,使得装入背包中物品的总价值最大?
01背包问题之另一种风格的描述:
为了让偷窃的商品价值最高,你该选择哪些商品?
简单算法
最简单的算法是:尝试各种可能的商品组合,并找出价值最高的组合。
这样显然是可行的,但是速度非常慢。在只有3件商品的情况下,你需要计算8个不同的集合;当有4件商品的时候,你需要计算16个不同的集合。每增加一件商品,需要计算的集合数都将翻倍!这种算法的运行时间是O(2ⁿ),真的是慢如蜗牛。
动态规划
解决这样问题的答案就是使用动态规划!下面来看看动态规划的工作原理。动态规划先解决子问题,再逐步解决大问题。
对于背包问题,你先解决小背包(子背包)问题,再逐步解决原来的问题。
比较有趣的一句话是:每个动态规划都从一个网格开始。
背包问题的网格如下:
网格的各行为商品,各列为不同容量(1~4磅)的背包。所有这些列你都需要,因为它们将帮助你计算子背包的价值。
网格最初是空的。你将填充其中的每个单元格,网格填满后,就找到了问题的答案!
1.吉他行
后面会列出计算这个网格中单元格值得公式,但现在我们先来一步一步做。首先来看第一行。
这是吉他行,意味着你将尝试将吉他装入背包。在每个单元格,都需要做一个简单的决定:偷不偷吉他?别忘了,你要找出一个价值最高的商品集合。
第一个单元格表示背包的的容量为1磅。吉他的重量也是1磅,这意味着它能装入背包!因此这个单元格包含吉他,价值为1500美元。
下面来填充网格。
与这个单元格一样,每个单元格都将包含当前可装入背包的所有商品。
来看下一个单元格。这个单元格表示背包容量为2磅,完全能够装下吉他!
这行的其他单元格也一样。别忘了,这是第一行,只有吉他可供你选择,换而言之,你假装现在还没发偷窃其他两件商品。
此时你很可能心存疑惑:原来的问题说的额是4磅的背包,我们为何要考虑容量为1磅、2磅等得背包呢?前面说过,动态规划从小问题着手,逐步解决大问题。这里解决的子问题将帮助你解决大问题。
别忘了,你要做的是让背包中商品的价值最大。这行表示的是当前的最大价值。它指出,如果你有一个容量4磅的背包,可在其中装入的商品的最大价值为1500美元。
你知道这不是最终解。随着算法往下执行,你将逐步修改最大价值。
2.音响行
我们来填充下一行——音响行。你现在处于第二行,可以偷窃的商品有吉他和音响。
我们先来看第一个单元格,它表示容量为1磅的背包。在此之前,可装入1磅背包的商品最大价值为1500美元。
该不该偷音响呢?
背包的容量为1磅,显然不能装下音响。由于容量为1磅的背包装不下音响,因此最大价值依然是1500美元。
接下来的两个单元格的情况与此相同。在这些单元格中,背包的容量分别为2磅和3磅,而以前的最大价值为1500美元。由于这些背包装不下音响,因此最大的价值保持不变。
背包容量为4磅呢?终于能够装下音响了!原来最大价值为1500美元,但如果在背包中装入音响而不是吉他,价值将为3000美元!因此还是偷音响吧。
你更新了最大价值。如果背包的容量为4磅,就能装入价值至少3000美元的商品。在这个网格中,你逐步地更新最大价值。
3.笔记本电脑行
下面以同样的方式处理笔记本电脑。笔记本电脑重3磅,没法将其装入1磅或者2磅的背包,因此前两个单元格的最大价值仍然是1500美元。
对于容量为3磅的背包,原来的最大价值为1500美元,但现在你可以选择偷窃价值2000美元的笔记本电脑而不是吉他,这样新的最大价值将为2000美元。
对于容量为4磅的背包,情况很有趣。这是非常重要的部分。当前的最大价值为3000美元,你可不偷音响,而偷笔记本电脑,但它只值2000美元。
价值没有原来高,但是等一等,笔记本电脑的重量只有3磅,背包还有1磅的重量没用!
在1磅的容量中,可装入的商品的最大价值是多少呢?你之前计算过。
根据之前计算的最大价值可知,在1磅的容量中可装入吉他,价值1500美元。因此,你需要做如下的比较:
你可能始终心存疑惑:为何计算小背包可装入的商品的最大价值呢?但愿你现在明白了其中的原因!**余下了空间时,你可根据这些子问题的答案来确定余下的空间可装入哪些商品。**笔记本电脑和吉他的总价值为3500美元,因此偷它们是更好的选择。
最终的网格类似于下面这样。
答案如下:将吉他和笔记本电脑装入背包时价值更高,为3500美元。
你可能认为,计算最后一个单元格的价值时,我使用了不同的公式。那是因为填充之前的单元格时,我故意避开了一些复杂的因素。其实,计算每个单元格的价值时,使用的公式都相同。这个公式如下。
你可以使用这个公式来计算每个单元格的价值,最终的网格将与前一个网格相同。现在你明白了为何要求解子问题了吧?你可以合并两个子问题的解来得到更大问题的解。
算法描述和代码实现:
算法的核心是思想,当清楚了整个过程,那么写代码就简单了,直接来模拟上述的一个过程:
在解决问题之前,为描述方便,首先定义一些变量:ViV_iVi表示第iii个物品的价值,WiW_iWi表示第 iii 个物品的质量,定义V(i,j)V(i,j)V(i,j):当前背包容量 jjj,前iii个物品最佳组合对应的价值,同时背包问题抽象化(X1,X2,…,Xn,其中Xi取0或1,表示第i个物品选或不选)(X1,X2,…,Xn,其中 Xi 取0或1,表示第 i 个物品选或不选)(X1,X2,…,Xn,其中Xi取0或1,表示第i个物品选或不选)
1、建立模型:即求max(V1X1+V2X2+...+VnXn)max(V_1X_1+V_2X_2+...+V_nX_n)max(V1X1+V2X2+...+VnXn)
2、寻找约束条件,V1X1+V2X2+...+VnXn<capacityV_1X_1+V_2X_2+...+V_nX_n< capacityV1X1+V2X2+...+VnXn<capacity
3、寻找递推关系式,面对当前商品有两种可能性:
包的容量比该商品体积小,装不下,此时的价值与前i−1i-1i−1个的价值是一样的,即V(i,j)=V(i−1,j)V(i,j)=V(i-1,j)V(i,j)=V(i−1,j);
还有足够的容量可以装该商品,但装了也不一定达到当前最优价值,所以在装与不装之间选择最优的一个,即V(i,j)=max{V(i−1,j),V(i−1,j−w(i))+v(i)}V(i,j)=max{V(i-1,j),V(i-1,j-w(i))+v(i)}V(i,j)=max{V(i−1,j),V(i−1,j−w(i))+v(i)}。
其中V(i−1,j)V(i-1,j)V(i−1,j)表示不装,V(i−1,j−w(i))+v(i)V(i-1,j-w(i))+v(i)V(i−1,j−w(i))+v(i)表示装了第iii个商品,背包容量减少w(i)w(i)w(i),但价值增加了v(i)v(i)v(i);
由此可以得出递推关系式:
j<w(i)V(i,j)=V(i−1,j)(装不下i,因此不考虑)j<w(i) V(i,j)=V(i-1,j) (装不下i,因此不考虑)j<w(i)V(i,j)=V(i−1,j)(装不下i,因此不考虑)
j>=w(i)V(i,j)=max{V(i−1,j),V(i−1,j−w(i))+v(i)}(装与不装选一个,装的时候的表达式)j>=w(i) V(i,j)=max{V(i-1,j),V(i-1,j-w(i))+v(i)}(装与不装选一个,装的时候的表达式)j>=w(i)V(i,j)=max{V(i−1,j),V(i−1,j−w(i))+v(i)}(装与不装选一个,装的时候的表达式)
这里需要解释一下,为什么能装的情况下,需要这样求解(这才是本问题的关键所在!):
可以这么理解,如果要到达V(i,j)V(i,j)V(i,j)这一个状态有几种方式?
肯定是两种,第一种是第iii件商品没有装进去,第二种是第iii件商品装进去了。没有装进去很好理解,就是V(i−1,j)V(i-1,j)V(i−1,j);装进去了怎么理解呢?如果装进去第iii件商品,那么装入之前是什么状态,肯定是V(i−1,j−w(i))V(i-1,j-w(i))V(i−1,j−w(i))。由于最优性原理(上文讲到),V(i−1,j−w(i))V(i-1,j-w(i))V(i−1,j−w(i))就是前面决策造成的一种状态,后面的决策就要构成最优策略。两种情况进行比较,得出最优。
import numpy as npdef solve(vlist,wlist,totalWeight,totalLength):resArr = np.zeros((totalLength+1,totalWeight+1),dtype=np.int32)for i in range(1,totalLength+1):for j in range(1,totalWeight+1):if wlist[i] <= j:resArr[i,j] = max(resArr[i-1,j-wlist[i]]+vlist[i],resArr[i-1,j])else:resArr[i,j] = resArr[i-1,j]return resArr[-1,-1]if __name__ == '__main__':v = [0,1500,2000,3000]w = [0,1,3,4]weight = 4n = 3result = solve(v,w,weight,n)print(result) # 3500
复杂度优化
以上方法的时间和空间复杂度均为 O(N*W),其中时间复杂度基本已经不能再优 化了,但空间复杂度却可以优化到 O(W)。
先考虑上面讲的基本思路如何实现,肯定是有一个主循环 i=1…N,每次算出来 二维数组 f[i][0…W]的所有值。那么,如果只用一个数组 f[0…W],能不能保证 第 i 次循环结束后 f[w]中表示的就是我们定义的状态 f[i][w]呢?f[i][w]是由 f[i-1][w]和 f[i-1][w-c[i]]两个子问题递推而来,能否保证在推 f[i][w]时(也 即在第 i 次主循环中推 f[w]时)能够得到 f[i-1][w]和 f[i-1][w-w[i]]的值呢? 事实上,这要求在每次主循环中我们以 v=V…0 的顺序推 f[w],这样才能保证推 f[v]时 f[v-w[i]]保存的是状态 f[i-1][w-w[i]]的值。改进后的代码如下:
def solve2(vlist,wlist,totalWeight,totalLength):resArr = np.zeros((totalWeight)+1,dtype=np.int32)for i in range(1,totalLength+1):for j in range(totalWeight,0,-1):if wlist[i] <= j:resArr[j] = max(resArr[j],resArr[j-wlist[i]]+vlist[i])return resArr[-1]if __name__ == '__main__':v = [0,60,100,120]w = [0,10,20,30]weight = 50n = 3result = solve2(v,w,weight,n)print(result)
再增加一件商品将如何呢
假设你发现还有第四件商品可偷——一个iPhone!(或许你会毫不犹豫的拿走,但是请别忘了问题的本身是要拿走价值最大的商品)
此时需要重新执行前面所做的计算吗?不需要。别忘了,动态规划逐步计算最大价值。到目前为止,计算出的最大价值如下:
这意味着背包容量为4磅时,你最多可偷价值3500美元的商品。但这是以前的情况,下面再添加表示iPhone的行。
我们还是从第一个单元格开始。iPhone可装入容量为1磅的背包。之前的最大价值为1500美元,但iPhone价值2000美元,因此该偷iPhone而不是吉他。
在下一个单元格中,你可装入iPhone和吉他。
对于第三个单元格,也没有比装入iPhone和吉他更好的选择了。
对于最后一个单元格,情况比较有趣。当前的最大价值为3500美元,但你可以偷iPhone,这将余下3磅的容量。
3磅容量的最大价值为2000美元!再加上iPhone价值2000美元,总价值为4000美元。新的最大价值诞生了!
最终的网格如下。
问题:沿着一列往下走,最大价值可能降低吗?
答案是:不可能。因为每次迭代时,你都存储的是当前的最大价值。最大价值不可能比以前低!
进一步思考
我们看到的求最优解的背包问题题目中,事实上有两种不太相同的问法。有的题 目要求“恰好装满背包”时的最优解,有的题目则并没有要求必须把背包装满。 一种区别这两种问法的实现方法是在初始化的时候有所不同。
如果是第一种问法,要求恰好装满背包,那么在初始化时除了 f[0]为 0 其它 f[1…W]均设为-∞,这样就可以保证最终得到的 f[N]是一种恰好装满背包的最优解。
如果并没有要求必须把背包装满,而是只希望价格尽量大,初始化时应该将 f[0…W]全部设为 0。
为什么呢?
可以这样理解:初始化的 f 数组事实上就是在没有任何物品可以放入 背包时的合法状态。如果要求背包恰好装满,那么此时只有容量为 0 的背包可能 被价值为 0 的 nothing“恰好装满”,其它容量的背包均没有合法的解,属于未 定义的状态,它们的值就都应该是-∞了。如果背包并非必须被装满,那么任何 容量的背包都有一个合法解“什么都不装”,这个解的价值为 0,所以初始时状 态的值也就全部为 0 了。
总结
01 背包问题是最基本的背包问题,它包含了背包问题中设计状态、方程的最基 本思想,另外,别的类型的背包问题往往也可以转换成 01 背包问题求解。故一 定要仔细体会上面基本思路的得出方法,状态转移方程的意义,以及最后怎样优 化的空间复杂度。
参考:
1./p/a66d5ce49df5
2./p/25f4a183ede5
—————————————————————————————————————————————————
博主码字不易,大家关注点个赞转发再走呗 ,您的三连是激发我创作的源动力^ - ^