动态规划
分治法
分治法是将问题划分为互不相交的子问题，递归的求解子问题，再将它们的解组合起来，求出原问题的解。
动态规划
动态规划是应用于子问题重叠的情况，即不同的子问题具有公共的子子问题。
最简单的动态规划问题是斐波那契数列问题，它既是递归中的典型例子也是动态规划的典型例子，在斐波那契之后将介绍典型的01背包问题，从而进一步理解动态规划。
一、斐波那契数列
斐波那契数列的递归求解方法：
#递归方法
def fib(n):
if n<=0: return 0
if n==1:return 1
return fib(n-1)+fib(n-2)
下面看看算法的执行流程，假如输入6，那么执行的递归树如下所示。
上面Fibonacci的例子，上面的递归的求解方式就是分治算法，由于它的子问题是相互相关的，此时利用分治法就做了很多重复的工作，它会反复求解那些公共子子问题。而动态规划算法对每一个子子问题只求解一次，将其保存在一个表格中，从而避免重复计算。
下面我们介绍两种方法来说明动态规划的算法：自顶向下的备忘录法和自底向上的方法。
1.自顶向下的备忘录法
#自顶向下——备忘录算法
def memo(n):
mydict={}
return fib_memo(n,mydict)
def fib_memo(n,mydict):
if n<=0: return 0
if n==1:return 1
if n in mydict:
return dict[n]
else:
value=fib_memo(n-1,mydict)+fib_memo(n-2,mydict)
mydict[str(n)]=value
return value
利用mydict字典来存放斐波拉契数列中的每一个值，由于是自顶往下递归，它还是会最先递归到mydict[3]，从此刻开始在往上计算，然后依次保存计算结果在mydict字典中，避免了重复运算。
2.自底向上的方法
自顶而下的方式来计算最终的结果，还是有一个递归的过程。既然最终是从fib(1)开始算，那么直接从fib(1)计算不就得了，先算子问题，再算父问题。
我们从接触斐波拉契数列开始，就是递归的方式，弄到最后，发现还是直接来方便很多啊。
#自下向上——动态规划算法
def fib_dp(n):
if n<=0: return 0
if n==1:return 1
a=1
b=1
for i in range(2,n):
a,b=b,a+b
return b
从上面的例子可以看到自顶向下的方式的动态规划其实包含了递归，而递归就会有额外的开销的；而使用自底向上的方式可以避免。看来斐波那契真是个好东西，递归的时候用它来入门，现在动态规划也是用它来入门。
二、01背包问题
动态规划则具有记忆性，通过填写表把所有已经解决的子问题答案纪录下来，在新问题里需要用到的子问题可以直接提取，避免了重复计算，从而节约了时间，所以在问题满足最优性原理之后，用动态规划解决问题的核心就在于填表，表填写完毕，最优解也就找到。
最优性原理是动态规划的基础，最优性原理是指**“多阶段决策过程的最优决策序列具有这样的性质：不论初始状态和初始决策如何，对于前面决策所造成的某一状态而言，其后各阶段的决策序列必须构成最优策略”**。
判断该问题是否满足最优性原理，采用反证法证明：
假设(X1，X2，…，Xn)是01背包问题的最优解，则有(X2，X3，…，Xn)是其子问题的最优解，假设(Y2，Y3，…，Yn)是上述问题的子问题最优解，则理应有(V2Y2+V3Y3+…+VnYn)+V1X1 > (V2X2+V3X3+…+VnXn)+V1X1；
然而(V2X2+V3X3+…+VnXn)+V1X1=(V1X1+V2X2+…+VnXn)，则有(V2Y2+V3Y3+…+VnYn)+V1X1 > (V1X1+V2X2+…+VnXn)；
该式子说明(X1，Y2，Y3，…，Yn)才是该01背包问题的最优解，这与最开始的假设(X1，X2，…，Xn)是01背包问题的最优解相矛盾，故01背包问题满足最优性原理。
假设我们现有以下4个物品，背包容量为8，物品的体积和价值如下表所示：
2.1 背包问题的表示
-
把背包问题抽象化（X1，X2，…，Xn，其中 Xi 取0或1，表示第 i 个物品选或不选），Vi表示第 i 个物品的价值，Wi表示第 i 个物品的体积（重量）；
-
建立模型，即求max(V1X1+V2X2+…+VnXn)；
约束条件，W1X1+W2X2+…+WnXn<capacity；
-
定义V(i,j)：表示前 i 个物品最佳组合对应的价值，当前背包容量 j；
-
寻找递推关系式，面对当前商品有两种可能性：
-
第一，包的容量比该商品体积小，装不下，此时的背包中的总价值与前i-1个的价值是一样的，即V(i,j)=V(i-1,j)，相当于不考虑当前物品所得到的价值；
-
第二，还有足够的容量可以装该商品，但装了也不一定达到当前最优价值，所以在装与不装之间选择最优的一个，即V(i,j)=max｛V(i-1,j)，V(i-1,j-w(i))+v(i)｝
其中V(i-1,j)表示不装，最终价值就是前面i-1的价值；
V(i-1,j-w(i))+v(i) 表示装了第i个商品，背包容量减少w(i)；用剩余的背包容量去装前面的物品，然后把总的价值加起来。
-
-
j<w(i) V(i,j)=V(i-1,j)
-
j>=w(i) V(i,j)=max｛ V(i-1,j)，V(i-1,j-w(i))+v(i) ｝
-
-
-
填表
- 首先初始化边界条件，V(0,j)=V(i,0)=0；
-
然后一行一行的填表
1）i=1，j=1，w(1)=2，v(1)=3，有j<w(1)，故V(1,1)=V(1-1,1)=0；
2）又如i=1，j=2，w(1)=2，v(1)=3，有j=w(1),故V(1,2)=max｛ V(1-1,2)，V(1-1,2-w(1))+v(1) ｝=max｛0，0+3｝=3；
3）如此下去，填到最后一个，i=4，j=8，w(4)=5，v(4)=6，有j>w(4)，故V(4,8)=max｛ V(4-1,8)，V(4-1,8-w(4))+v(4) ｝=max{ V(3,8), V(3,3)+V(4)} =max｛9，4+6｝=10；
转化为程序为：
import numpy as np
def solve(vlist,wlist,totalWeight,totalLength):
resArr = np.zeros((totalLength+1,totalWeight+1),dtype=np.int32)
for i in range(1,totalLength+1):
for j in range(1,totalWeight+1):
if wlist[i] <= j:
resArr[i,j] = max(resArr[i-1,j-wlist[i]]+vlist[i],resArr[i-1,j])
else:
resArr[i,j] = resArr[i-1,j]
return resArr[-1,-1]
if __name__ == '__main__':
v = [0,3,4,5,6]
w = [0,2,3,4,5]
weight = 8
n = 4
result = solve(v,w,weight,n)
print(result)
2.2 背包中物品的组成
表格填完，最优解即是V(number,capacity)=V(4,8)=10，但还不知道解由哪些商品组成，故要根据最优解回溯找出解的组成，根据填表的原理可以有如下的寻解方式：
-
V(i,j)=V(i-1,j)时，说明没有选择第i 个商品，则回到V(i-1,j)；
-
V(i,j)=V(i-1,j-w(i))+v(i)实时，说明装了第i个商品，该商品是最优解组成的一部分，随后我们得回到装该商品之前，即回到V(i-1,j-w(i))；
-
一直遍历到i＝0结束为止，所有解的组成都会找到。
正如在上述例子中：
-
最优解为V(4,8)=10，而V(4,8)!=V(3,8)却有V(4,8)=V(3,8-w(4))+v(4)=V(3,3)+6=4+6=10，所以第4件商品被选中，并且回到V(3,8-w(4))=V(3,3)；
-
有V(3,3)=V(2,3)=4，所以第3件商品没被选择，回到V(2,3)；
-
而V(2,3)!=V(1,3)却有V(2,3)=V(1,3-w(2))+v(2)=V(1,0)+4=0+4=4，所以第2件商品被选中，并且回到V(1,3-w(2))=V(1,0)；
-
有V(1,0)=V(0,0)=0，所以第1件商品没被选择；
到此，01背包问题已经解决，利用动态规划解决此问题的效率即是填写此张表的效率，所以动态规划的时间效率为O(numbercapacity)=O(nc)，由于用到二维数组存储子问题的解，所以动态规划的空间效率为O(n*c)；
参考文献：
https://www.cnblogs.com/Christal-R/p/Dynamic_programming.html
https://www.cnblogs.com/cthon/p/9251909.html
转载：https://blog.csdn.net/qq_33414271/article/details/100847219