【算法图解】动态规划

背包问题

假如有个小偷，背着可装4磅东西的背包，可盗窃的物品有如下三件：

音响	笔记本电脑	吉他
3000美元	2000美元	1500美元
4磅	3磅	1磅

为了让盗窃的总价值最高，该选择哪些商品？

动态规划解法

动态规划解法做成了如下的表格：

	1	2	3	4
吉他	1500美元(G)	1500美元(G)	1500美元(G)	1500美元(G)
音响	1500美元(G)	1500美元(G)	1500美元(G)	3000美元(S)
笔记本电脑	1500美元(G)	1500美元(G)	2000美元(L)	3500美元(LG)

答案：将吉他和笔记本电脑装入背包时价值最高，为3500美元。

计算每个单元格价值时，运用如下公式：

cell[i][j] =
max{ 上一个单元格的值(cell[i-1][j]) ，当前商品价值(cell[i][j-1])+剩余空间价值(cell[i-1][j-当前物品重量])

代码表现

# -*- coding: utf-8 -*-
def bag(n,c,w,p):
    res=[[-1 for j in range(c+1)]for i in range(n+1)]
    for j in range(c+1):
        #第0行全部赋值为0，物品编号从1开始.为了下面赋值方便
        res[0][j]=0
    for i in range(1,n+1):
        for j in range(1,c+1):
            res[i][j]=res[i-1][j]
            print res
            #生成了n*c有效矩阵，以下公式w[i-1],p[i-1]代表从第一个元素w[0],p[0]开始取。
            if(j>=w[i-1]) and res[i-1][j-w[i-1]]+p[i-1]>res[i][j]:
                res[i][j]=res[i-1][j-w[i-1]]+p[i-1]
    return res
#以下代码功能：标记出有放入背包的物品
#反过来标记，在相同价值情况下，后一件物品比前一件物品的最大价值大，则表示物品i#有被加入到背包，x数组设置为True。设初始为j=c。
def show(n,c,w,res):
    print '最大价值为:',res[n][c]
    x=[False for i in range(n)]
    j=c
    for i in range(1,n+1):
        if res[i][j]>res[i-1][j]:
            x[i-1]=True
            j-=w[i-1]
    print '选择的物品为:'
    for i in range(n):
        if x[i]:
            print '第',i,'个,'
    print''
if __name__=='__main__':
    n=3
    c=4
    w=[1,3,4] #这里重量要按从小到大排序
    p=[1500,2000,3000]
    res=bag(n,c,w,p)
    show(n,c,w,res)

理论上来说，第33行的重量无所谓顺序，但是此算法转化为代码时，因为代码的一些缺陷，导致必须要按从小到大排序才能使程序顺利运行。

旅行行程最优化

假设你要去伦敦度假，假期两天，你想去浏览的地方很多，但是没法全部浏览到，因此有如下的单子：

名胜	时间	评分
威斯敏斯特教堂	0.5天	7
环球剧场	0.5天	6
英国国家美术馆	1天	9
大英博物馆	2天	9
圣保罗大教堂	0.5天	8

这也可以转化为一个背包问题，可列出如下列表：

	1/2	1	3/2	2
威斯敏斯特教堂(W)	7(W)	7(W)	7(W)	7(W)
环球剧场(G)	7(W)	13(WG)	13(WG)	13(WG)
英国国家美术馆(N)	7(W)	13(WG)	16(WN)	22(WGN)
大英博物馆(B)	7(W)	13(WG)	16(WN)	22(WGN)
圣保罗大教堂(S)	7(W)	15(WS)	21(WGS)	24(WNS)

动态规划问题特征

• 动态规划问题可以在给定约束条件下找到最优解。
• 问题可分解成彼此独立且离散的子问题时，就可使用动态规划来解决。
• 每种动态规划都涉及网格。