Foreword
遇到一个涉及到很多球根据约束条件,选取最多数量的球的问题,类似于背包问题.
基本0/1背包
问题:有n个物品,物品不重复,每个物品对应价值为price[i],对应重量是weight[i],背包最大载重是w,求背包能装的最大价值的是多少,或者说背包要怎么装才能得到最大价值.
因为对于每个物品而言只有两种选择,拿或者不拿,对应0/1,当然可以用暴力搜索直接遍历一遍所有的得到解,但是太慢了,要合理解决这个问题,就要用到动态规划来求解了.
动态规划
以前经常遇到动态规划,只是一直没闹懂什么是动态规划,要如何动态规划.
基本概念
- 动态规划:可以将问题拆解成独立的子问题,并且可以定义问题的状态,状态间的关系,使得问题可以通过递归式的方法去解决.
- 子问题:子问题是十分类似的,可以使用相同的方法继续分割成更小的子问题,并且子问题依然独立,子问题的解是最优的(子问题三要素:相同子问题,最优子结构,无后效性)
绝大多数的递归式的算法都可以说是运用了动态规划的思想(不能反过来说),刚开始只看定义的话会比较苦恼,完全没看明白动态规划到底是什么.
一般来说解决动态规划的问题有这么几步:
- 寻找子问题,通过子问题能把问题的规模变小,从而可以让我们先去解决最小的问题,然后再往大问题上去解决
- 推算状态转移方程,简而言之就是子问题如何层层上升到原问题的,肯定可以用一个表达式来描述(不一定完全)
- 确定边界条件,也就是何时停止递推,一般都与题目中的限制有关系
- 实现与优化:简单的就直接递归,复杂的还是要迭代,一般来说都是需要优化的.
实例分析
首先要从0/1背包问题中去寻找子问题,最终的问题是从n个物品中选择j个物品,并且重量不超过w,那么要缩小问题,变成子问题,就是:
- n-1个物品中,选择j-1个物品,并且重量不超过w-weight[j] (选择j)，总价值为P(j-1,W-weight[j])
- n-1个物品中,选择j-1个物品,并且重量不超过w (没选择j)，总价值为P(j-1,W)
比较两个子问题的总价值,选择最好的那个方案即可.
这样就把一个大问题分成了两个子问题,子问题可以更抽象一些.
子问题为P(i,W),其表示在i个物品中,挑选总重量不超过W的物品,每个物品价值为price[i],使得总价值最大.
其实这里的P(i,W)就是一个状态,描述的就是在i和W的情况下的原问题一个状态.
寻找这个状态就是第一步,就是要将原来的问题,抽象化,变成一个可以用来描述这个问题的一个函数式.
找到了子问题,现在就要找状态转移方程了,经过上面的分析,其实可以知道就是取两种可能中的价值最大的那一种作为状态转换方程.
P(j,W) = MAX(p(j-1,W),p(j-1,W-weight[j])+price[j])
通过上式基本就描述了:在j个物体重寻找总重不超过W的物品的最大值 等于在 在j-1个物体重寻找总重不超过W的总价值 和 在j-1个物体中寻找总重不超过W-weight[j]的总价+第j个物品的价值 中取较大的那个,这样得到的结果自然就是问题的最优解.
而这里的每一个子问题都可以按照这个思路继续往下划分,这样我们就得到了状态转移方程.
接下来就是确定边界条件,也就是子问题要划分到什么程度,其实也就是递归的结束点,也就是递归到最后一个物品的时候或者是总重用完的时候就开始向上返回,从而得到最终的结果.
code
price = [0,60,100,120,7,6,5,4,3,2,1]
weight = [0,10,20,30,14,15,16,17,8,9,10]
W = 70
n = 10
def dp(i,w):
if i == 0 or w <= 0 :
return 0
a = b = 0
if w >= weight[i]:
a = max(dp(i-1,w),dp(i-1,w-weight[i]) + price[i])
else:
b = dp(i-1,w)
return max(a,b)
print(dp(n,W))
简单说就是放得下的情况下,求放的下和放不下的两种情况的最大值,放不下的情况下,则是直接跳过当前物品，进入下一个物品的判断。
Summary
一般来说用递归解dp是非常浪费内存和时间的，而且其实际复杂度也非常高O(nw).所以一般来说都会写成迭代的方式,然后再记忆存储,优化一下存储的空间等.
Quote
http://blog.csdn.net/sun897949163/article/details/52077460
https://www.zhihu.com/question/23995189
http://blog.csdn.net/sj13051180/article/details/6687674
http://blog.csdn.net/liyingjie01/article/details/51426021
http://shmilyaw-hotmail-com.iteye.com/blog/2009761
http://www.hawstein.com/posts/dp-novice-to-advanced.html