进阶算法：动态规划 (笔记)

很久以前考过计算机软考中级，看过推荐教材里的算法篇章。少有应用渐渐忘切，直到最近刷题重遇该问题。在多变的应用中，灵活运用是关键。

动态规划是跟递归关联的，着重于计算重叠子问题的最优解的算法。

经典的案例 -- “背包问题”^[1]：
假设一个背包的最大承重为W，现有n件重量为w，价值为v的物件，求可以装入背包的物品的最大价值。

其中，v = [4,5,10,15,13], w = [3,4,7,8,7], n = 5, W = 17

用数学公式表达为：

c(i,w) 的值为：

            1)  0,  i = 0 或 w = 0
            2)  c(i-1, w)   , w(i) > w
            3)  max{c(i-1, w-w(i)) + v(i), c(i-1, w)},    i > 0 且 w(i) < w

转换为Python源码：

class Solution:
    def solve(self, v, w, n, W):
        c=[]
        w.insert(0, 0)
        for i in range(n+1):
            c.append([])
            for w0 in range(W+1):
                c[i].append(0)
        for i in range(1, n+1):
            c[i][0]=0
            for w0 in range(1, W+1):
                if w[i]<=w0:
                    if v[i-1]+c[i-1][w0-w[i]]>=c[i-1][w0]:
                        c[i][w0]=v[i-1]+c[i-1][w0-w[i]]
                    else:
                        c[i][w0]=c[i-1][w0]
                else:
                    c[i][w0]=c[i-1][w0]
        return c[-1][-1]                
        
print(Solution().solve([4,5,16,11,15], [3,4,7,8,6], 5, 17)) 

通过一些与本案例类似的代码对比，发现值得注意的地方：一是数据的保存方式为数组等通过数字索引读取的数据结构，二是数据的索引于数据间的值或差值紧密相关。

1. 本题案例和Python代码使用的伪码来源于全国计算机技术与软件专业技术资格（水平）考试指定用书--《软件设计师教程》（第三版）（修订版）胡圣明主编，原始材料数据为有序，修改为无序 ↩