1、主要思想
从最简单情况开始到达所需找零的循环，其每一步都依靠以前的最优解来得到本步骤的最优解，直到得到答案。
2、例子
（1）找零兑换问题
1）引入
假设你为一家自动售货机厂家编程序，自动售货机要每次找给顾客最少数量硬币； 假设某次顾客投进$1纸币，买了ȼ37的东西，要找ȼ63，那么最少数量就是： 2个quarter（ȼ25）、 1个dime（ȼ10）和3个penny（ȼ1），一共6个 但面对特殊的货币体系，如ȼ21也在货币体系中时，该如何解决呢？
2）思路
动态规划算法采用了一种更有条理的方式来得到问题的解，找零兑换的动态规划算法从最简单的“1分钱找零”的最优解开始， 逐步递加上去， 直到我们需要的找零钱数。 在找零递加的过程中， 设法保持每一分钱的递加都是最优解， 一直加到求解找零钱数， 自然得到最优解。 递加的过程能保持最优解的关键是， 其依赖于更少钱数最优解的简单计算， 而更少钱数的最优解已经得到了。问题的最优解包含了更小规模子问题的最优解， 这是一个最优化问题能够用动态规划策略解决的必要条件。 以下图为例，采用动态规划来解决11分钱的兑换问题，从1分钱兑换开始，逐步建立一个兑换表。 计算11分钱的兑换法， 我们做如下几步： 首先减去1分硬币，剩下10分钱查表最优解是1 然后减去5分硬币，剩下6分钱查表最优解是2 最后减去10分硬币，剩下1分钱查表最优解是1 通过上述最小值得到最优解： 2个硬币
3）代码实现
def dpMakeChange(coinValueList
,change
,minCoins
,coinsUsed
):
for cents
in range(change
+1):
coinCount
= cents
newCoin
= 1
for j
in [c
for c
in coinValueList
if c
<= cents
]:
if minCoins
[cents
-j
] + 1 < coinCount
:
coinCount
= minCoins
[cents
-j
]+1
newCoin
= j
minCoins
[cents
] = coinCount
coinsUsed
[cents
] = newCoin
return minCoins
[change
]
def printCoins(coinsUsed
,change
):
coin
= change
while coin
> 0:
thisCoin
= coinsUsed
[coin
]
print(thisCoin
)
coin
= coin
- thisCoin
if __name__
== '__main__':
amnt
= 100
clist
= [1,5,10,21,25]
coinsUsed
= [0]*(amnt
+1)
coinCount
= [0]*(amnt
+1)
print("Making change for",amnt
,"requires")
print(dpMakeChange
(clist
,amnt
,coinCount
,coinsUsed
),"coins")
print("They are:")
printCoins
(coinsUsed
,amnt
)
print("The used list is as follows:")
print(coinsUsed
)
（2）图书馆大盗问题
1）引入
大盗潜入博物馆， 面前有5件宝物， 分别有重量和价值， 大盗的背包仅能负重20公斤， 请问如何选择宝物， 总价值最高？
2）思路
我们把m(i, W)记为：前i(1<=i<=5)个宝物中，组合不超过W，(1<=W<=20) 重量，得到的最大价值，m(i, W)应该是m(i-1, W)和m(i-1, W-Wi)+vi，两者最大值，我们从m(1, 1)开始计算到m(5, 20)
3）代码实现
①动态规划
tr
= [None,{'w':2,'v':3},{'w':3,'v':4},{'w':4,'v':8},{'w':5,'v':8},{'w':9,'v':10}]
max_w
= 20
m
= {(i
,w
):0 for i
in range(len(tr
)) for w
in range(max_w
+1)}
for i
in range(1,len(tr
)):
for w
in range(1,max_w
+ 1):
if tr
[i
]['w'] > w
:
m
[(i
,w
)] = m
[(i
-1,w
)]
else:
m
[(i
, w
)] = max(m
[(i
- 1, w
)],m
[(i
- 1, w
-tr
[i
]['w'])]+tr
[i
]['v'])
print(m
[(len(tr
)-1,max_w
)])
②带记忆化的递归算法
tr
= {(2,3),(3,4),(4,8),(5,8),(9,10)}
max_w
= 20
m
= {}
def thief(tr
,w
):
if tr
==set() or w
==0:
m
[(tuple(tr
),w
)] = 0
return 0
elif (tuple(tr
),w
) in m
:
return m
[(tuple(tr
),w
)]
else:
vmax
= 0
for t
in tr
:
if t
[0]<=w
:
v
= thief
(tr
-{t
},w
-t
[0])+t
[1]
vmax
= max(vmax
,v
)
m
[(tuple(tr
),w
)] =vmax
return vmax
print(thief
(tr
,max_w
))
