动态规划是将原始问题划分为若干个子问题，通过仅求解每个子问题一次，并将其结果保存在一个表结构中，以后用到的时候直接存取的方法。
2、适用于动态规划的问题 ① 优化子结构优化子结构，即一个问题的优化解包含了子问题的优化解。
② 重叠子问题在问题求解过程中，很多子问题的解被多次使用。
3、动态规划算法步骤 ① 分析优化解的结构 ② 建立状态转移方程（递归方程） ③ 自底向上地求解各个子问题一是计算优化解的代价并保存
二是获取构造最优解的信息并保存
④ 根据构造最优解的信息来构造优化解 二、动态规划求解0-1背包问题给定n种物品和一个背包，物品i的重量是， 价值 , 背包承重为C, 问如何选择装入背包的物品，使装入背包中的物品的总价值最大？
以下方算例为例，求解0-1背包问题。
| 物品 | 重量 | 价值 |
|---|---|---|
| 1 | 2 | 6 |
| 2 | 2 | 3 |
| 3 | 6 | 5 |
| 4 | 5 | 4 |
| 5 | 4 | 6 |
背包最大承重C为10。
1、基本模型 ① 分析优化解结构（1）
（2）
（3）
子问题v[i][j]表示只允许前i件物品放入容量为j的背包内可以获得的最大价值。
② 建立状态转移方程（1） 第一种情况
若第i件物品重量大于背包最大承重j，那么该子问题转化为前i-1件物品放入容量j背包内可以获得的最大价值，即
v[i][j] = v[i-1][j]
（2） 第二种情况
若第i件物品重量小于等于背包最大承重j，那么该子问题转化为 前i-1件物品放入容量j背包内可以获得的最大价值 与 前i-1件物品放入容量为j-背包内可以获得的最大价值 的最大值，即
v[i][j] = max {v[i-1][j],v[i-1][j-]}
③ 自底向上地求解各个子问题一是计算优化解的代价并保存
二是获取构造最优解的信息并保存
④ 根据构造最优解的信息来构造优化解该问题最优解的值即为v[n][C]
2、代码求解import numpy as np
# 求解0-1背包问题:n为物品数量；weight为背包最大承重；
# weight_list为物品重量表；value_list为物品价值表；
def bag(n, weight, weight_list, value_list):
# value_mat保存最优解的代价
value_mat = np.zeros((n + 1, weight + 1))
# object_mat保存获取最优解的信息
object_mat = [[] for i in range(n + 1)]
# 自底向上地求解各个子问题
for i in range(1, n + 1):
for j in range(weight + 1):
# 第一种情况
if weight_list[i - 1] > j:
value_mat[i][j] = value_mat[i - 1][j]
object_mat[i].append(0)
# 第二种情况
else:
if value_mat[i - 1][j] >= value_list[i - 1] + value_mat[i - 1][j - weight_list[i - 1]]:
value_mat[i][j] = value_mat[i - 1][j]
object_mat[i].append(0)
else:
value_mat[i][j] = value_list[i - 1] + value_mat[i - 1][j - weight_list[i - 1]]
object_mat[i].append(i)
# 求解该问题的最优解
best_value = value_mat[n][weight]
object_list = []
x = n
y = weight
# 求解获取该问题最优解的信息
while x > 0 and y > 0:
if object_mat[x][y] != 0:
object_list.append(object_mat[x][y])
x -= 1
y -= weight_list[x - 1]
else:
x -= 1
object_list.reverse()
# 返回最优解及其信息
return best_value, object_list
# 求解该算例
value, objects = bag(5, 10, [2, 2, 6, 5, 4], [6, 3, 5, 4, 6])
print(value, objects)
3、输出结果
15.0 [1, 2, 5]
