动态规划算法（dynamic programming algorithm）
动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。
概念：把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，得到最终解。
基本思想：将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解（与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次）。
基本模型：
(1)确定问题的决策对象。
(2)对决策过程划分阶段。
(3)对各阶段确定状态变量。
(4)根据状态变量确定费用函数和目标函数。
(5)建立各阶段状态变量的转移过程，确定状态转移方程。
适用条件：
（1）最优化原理（最优子结构性质）：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。
（2）无后效性：将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。
（3）子问题的重叠性：动态规划将原来具有指数级时间复杂度的搜索算法改进成了具有多项式时间复杂度的算法。其中的关键在于解决冗余，这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其它的算法。
假设你要去野营，你有一个容量为6磅的背包，需要决定该携带下面的哪些东西，其中每样东西都有其相应的价值，价值越大意味着越重要。
| 重量 |
价值 |
|
| 水 |
3 |
10 |
| 书 |
1 |
3 |
| 食物 |
2 |
9 |
| 夹克 |
2 |
5 |
| 相机 |
1 |
6 |
（1）我们把这个问题分解，给物品排个序，按顺序计算（顺序是不影响结果的，可以随意）。
从你的背包容量只能装1磅开始，承重1磅时，第一个水装不下，当前最大价值为0，第二个书可以最大价值更新为3，第三、第四都不能装，最大价值依然不变等于3，第五个可以装，此时判断它的价值与前面的最大价值，比之前大，则更新最大价值为6，这样就得到承重1磅的背包你可以选择的最大价值物品是相机。
接下来承重2磅、3磅、4磅、5磅、6磅时同理，为了直观看到结果，我们建立一个表格，列表示背包的承重，行表示物品，行列定位的格子值就代表当前背包承重下，可以获取的物品的最大价值（每个格子只考虑装当前位置及之前的物品价值，之后的暂不考虑），所以得到如下图所示表格（表格的作用是用来观察结果之间的联系，建立状态转移方程，所以当你问题的子问题很大时，不用全部列出来，很麻烦，列出一部分找到方程就行）
| 0 |
1 |
2 |
3 |
4 |
5 |
6 |
| 无 |
0 |
0 |
0 |
0 |
0 |
0 |
| 1（水10） |
0 |
0 | 10 |
10 |
10 | 10 |
| 2（书3） |
3 |
3 | 10 |
13 | 13 | 13 |
| 3（食9） |
3 |
9 | 12 | 13 |
19 | 22 |
| 4（衣5） |
3 |
9 |
12 |
14 | 19 |
22 |
| 5（相6） |
6 |
9 |
15 | 18 |
20 | 25 |
（2）由上表，可以看到，背包承重为6磅时，可以装的东西最大价值是25，所以建立如下状态转移方程。
'''当前物品重量小于背包承重时，需要判断当前物品价值加上剩余背包承重可装的最大价值的物品价值是否大于上面一个格子的价值.等于背包承重时需要判断当前物品价值和上面一个格子的价值比较。'''if j >= values[i-1][0]:surplus = j - values[i-1][0] # 计算背包剩余承重new_values = values[i-1][1] + grid[i-1][surplus]grid[i][j] = max(new_values, grid[i-1][j])else:grid[i][j] = grid[i-1][j]
（3）为了记录下在最大价值时携带了哪些物品，我们可以观察列表，但最大价值为25（5，6）时，25与它上面一个格子值不同，则证明包含当前的相机，然后减去相机重量，物品也减1---->到（4，5）这个位置，价值与（3，5）相同，则没包含当前物品，物品减1，剩余承重不变---->到（3，5），与（2，5）相比变了，则包含它，减去它2磅重量，物品减1---->到（2，3)......
| 0 |
1 |
2 |
3 |
4 |
5 |
6 |
| 无 |
0 |
0 |
0 |
0 |
0 |
0 |
| 1（水10） |
0 |
0 | 10 | 10 |
10 | 10 |
| 2（书3） |
3 |
3 | 10 | 13 | 13 | 13 |
| 3（食9） |
3 |
9 | 12 | 13 |
19 | 22 |
| 4（衣5） |
3 |
9 |
12 |
14 | 19 | 22 |
| 5（相6） |
6 |
9 |
15 | 18 |
20 | 25 |
代码实现：
items = [0 for i in range(7)]# 5种东西thing_num = 5bag_weight = 6while thing_num >= 1:i = thing_numif grid[i][bag_weight] == grid[i-1][bag_weight]:= 0else:= 1bag_weight -= values[i-1][0]thing_num -= 1
（4）最后得出承重6磅的背包携带水、食物、相机可获得最大价值，以下为完整代码。
# 先将每种物质属性用字典表示出来def property():property = {}property['water'] = [3, 10] # 第一个数表示重量，第二个表示价值property['book'] = [1, 3]property['food'] = [2, 9]property['jack'] = [2, 5]property['camera'] = [1, 6]return propertydef solve(pro):'''解决此问题需要建立一个6行7列的二维列表，行代表不同物品，列代表背包承重，每个格子存放当前背包容量下可装物品的最大价值(因为每一个结果依赖于前一个结果，所以虽然只有5种物品，却建立6行，第一行用0来表示未填装任何物品的状态)多一列因为列表索引从0开始，要表示1到6磅，免得索引还得减一使代码复杂了。'''grid = []for k in range(6):grid.append([])for g in range(7):grid[k].append(0)# values列表由五个子列表组成，子列表里面存放每个物品的重量和价值。values = list(pro.values())for i in range(1, 6): # 从第二行（第一个物品）开始计算for j in range(1, 7): # 列代表背包承重1-6磅'''当前物品重量小于背包承重时，需要判断当前物品价值加上剩余背包承重可装的最大价值的物品价值是否大于上面一个格子的价值.等于背包承重时需要判断当前物品价值和上面一个格子的价值比较。'''if j >= values[i-1][0]:surplus = j - values[i-1][0] # 计算背包剩余承重new_values = values[i-1][1] + grid[i-1][surplus]grid[i][j] = max(new_values, grid[i-1][j])else:grid[i][j] = grid[i-1][j]# 建立一个列表记录可承重的最大价值物品，0代表没有，1代表有items = [0 for i in range(7)]# 5种东西thing_num = 5bag_weight = 6while thing_num >= 1:i = thing_numif grid[i][bag_weight] == grid[i-1][bag_weight]:items[i] = 0else:items[i] = 1bag_weight -= values[i-1][0]thing_num -= 1return grid, itemsdef main():pro = property()grid, items = solve(pro)print('6磅容量的背包可以装下的物品的最大价值是{}'.format(grid[-1][-1]))pro_ls = list(pro.keys())take_things = []for i in range(7):if items[i] == 1:take_things.append(pro_ls[i-1])print('这些物品分别是{}'.format(take_things))main()