文档介绍：. .
优选
有8万元的投资可以投给3个过目，每个工程在不同筒子数额下〔以万元为单位〕的利润如下表
投资额
盈利
工程
0
1
2
3
4
5
6
7
8
工程1
0
态转移方程。
这里举一个01背包问题的例子：
你现在想买一大堆算法书，需要很多钱，所以你打算去抢一个商店，这个商店一共有n个商品。问题在于，你只能最多拿 W kg 的东西。wi和vi分别表示第i个商品的重量和价值。我们的目标就是在能拿的下的情况下，获得最大价值，求解哪些物品可以放进背包。对于每一个商品你有两个选择：拿或者不拿。
首先我们要做的就是要找到"子问题〞是什么，我们发现，每次背包新装进一个物品，就可以把剩余的承重能力作为一个新的背包来求解，一直递推到承重为0的背包问题：
. .
优选
作为一个聪明的贼，你用m[i,w]表示偷到商品的总价值，其中i表示一共多少个商品，w表示总重量，所以求解m[i,w]就是我们的子问题，那么你看到某一个商品i的时候，如何决定是不是要装进背包，有以下几点考虑：
该物品的重量大于背包的总重量，不考虑，换下一个商品；
该商品的重量小于背包的总重量，那么我们尝试把它装进去，如果装不下就把其他东西换出来，看看装进去后的总价值是不是更高了，否那么还是按照之前的装法；
极端情况，所有的物品都装不下或者背包的承重能力为0，那么总价值都是0；
由以上的分析，我们可以得出m[i,w]的状态转移方程为：
有了状态转移方程，那么写起代码来就非常简单了，首先看一下自顶向下的递归方式，比较容易理解：
*!/usr/bin/env python
* coding:utf-8
cache={}
items=range(0,9)
weights=[10,1,5,9,10,7,3,12,5]
values=[10,20,30,15,40,6,9,12,18]
* 最大承重能力
W=4
defm(i,w):
ifstr(i)+','+str(w)incache:
returncache[str(i)+','+str(w)]
result=0
* 特殊情况
ifi==0orw==0:
return0
* w < w[i]
ifw<weights[i]:
result=m(i-1,w)
* w >= w[i]
ifw>=weights[i]:
* 把第i个物品放入背包后的总价值
take_it=m(i-1,w-weights[i])+values[i]
. .
优选
* 不把第i个物品放入背包的总价值
ignore_it=m(i-1,w)
* 哪个策略总价值高用哪个
result=max(take_it,ignore_it)
iftake_it>ignore_it:
print'take ',i
else:
print'did not take',i
cache[str(i)+','+str(w)]=result
returnresult
if__name__=='__main__':
* 背包把所有东西都能装进去做假设开场
printm(len(i