动态规划之背包问题

48 sec read

背包问题(Knapsack problem)是动态规划的经典问题。动态规划的基础是递归,和分治一样,都是假设子问题已经解决,由子问题的解组合计算得到父问题的解,类似裴波那契数列中的递推式如f(n) = f(n-1) + f(n-2)。但在递归的过程中会出现重复计算子问题的现象,为了避免重复计算,用一个表格记录子问题的结果供查找,从下往上进行递推。找递推式(or 状态转移方程)的思路一般是由最终状态往前回溯,考察解答最终问题需要哪些子问题。

背包问题,有很多中类型,常见的有:

  • 01背包(ZeroOnePack): 有N件物品和一个容量为V的背包,每种物品均只有一件。第i件物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使价值总和最大。
  • 完全背包(CompletePack): 有N种物品和一个容量为V的背包,每种物品都有无限件可用。第i种物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。
  • 多重背包(MultiplePack): 有N种物品和一个容量为V的背包,第i种物品最多有n[i]件可用。每件费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。

01背包

动态规划的核心过程有两部分,一个是找出问题的“子状态”,再一个就是建立“状态转移方程”(所谓的递推公式)。欲求背包能够获得的总价值,即求前i个物体放入容量为m背包的最大价值c[i][m]

  • w[i]:第i个物体的重量
  • p[i]:第i个物体的价值
  • c[i][j]:前i个物体放入容量为j 包的最大价值
  • c[i-1][j]:前i-1个物体放入容量为j 包的最大价值
  • c[i-1][j-w[i]]:前i-1个物体放入容量为j-w[i] 包的最大价值

以下通过表格来说状态转移方程:

这里是用二维数组存储的,可以把空间优化,用一维数组存储。 用c[0..m]表示,c[m]表示把前i件物品放入容量为m的背包里得到的价值。把i从1~n(n件)循环后,最后c[m]表示所求最大值。

这里c[m]就相当于二维数组的c[i][m]。那么,如何得到c[i-1][m]和c[i-1][m-w[i]]+p[i]?

首先要知道,我们是通过i从1到n的循环来依次表示前i件物品存入的状态。即:for i=1..N。现在思考如何能在是c[m]表示当前状态是容量为m的背包所得价值,而又使c[m]和c[m-w[i]]+p[i]标签前一状态的价值?

答案是逆转:

分析上面的代码:当内循环是逆序时,就可以保证后一个c[m]和c[m-w[i]]+p[i]是前一状态的!这里给大家一组测试数据:

相关代码实现:

以上方法的时间和空间复杂度为O(n*W),其中时间复杂度已经不能再优化了,但是空间复杂度可以优化到O(W),优化后的代码如下:

上述代码实现为01背包问题的实现原理,如需在实际情况中采用类似的思路解决问题,可以使用Google Optimization Tools工具,具体代码如下:

参考链接:

完全背包

完全背包(CompletePack): 有N种物品和一个容量为V的背包,每种物品都有无限件可用。第i种物品的重量为w [i],价值是p[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。完全背包按其思路仍然可以用一个二维数组来写出:

同样可以转换成一维数组来表示:

完全和01背包的区别,这里的内循环是顺序的,而01背包是逆序的。为何完全背包可以这么写?原因是为了max中的两项是前一状态值。那么这里,我们顺序写,这里的max中的两项当然就是当前状态的值了,为何? 因为每种背包都是无限的。当我们把i从1到N循环时,c[m]表示容量为m在前i种背包时所得的价值,这里我们要添加的不是前一个背包,而是当前背包。所以我们要考虑的当然是当前状态。

参考链接:

多重背包

多重背包(MultiplePack): 有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用,每件重量是w[i],价值是p[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。

这题目和完全背包问题很类似。基本的方程只需将完全背包问题的方程略微一改即可,因为对于第i种物品有n[i]+1种策略:取0件,取1件……取n[i]件。令f[i][v]表示前i种物品恰放入一个容量为v的背包的最大权值,则有状态转移方程:

其他参考:

打赏作者
微信支付标点符 wechat qrcode
支付宝标点符 alipay qrcode

C语言学习:size_t

在学习C语言的时候,遇到了一个新的数据类型size_t,截止目前也没有完全理清这个类似的具体场景及出现的原因。
44 sec read

C语言学习:main()函数的正确写法

C语言虽然是一门古老的语言,但是其标准一直在完善,所以很多以前支持的语法在到当前已经不能在使用了。 C语言的版
41 sec read

Scipy数学函数的Scala实现

最近在推进项目的时候,遇到需要将线下的Python代码转化成线上的集群代码,由于机器代码环境是Scala,所以
4 min read

发表评论

电子邮件地址不会被公开。 必填项已用*标注