动态规划

1. 模型原理

动态规划是运筹学的一个分支，通常用来解决多阶段决策过程最优化问题。动态规划的基本想法就是将原问题转换为一系列相互联系的子问题，然后通过逐层地推来求得最后的解。目前，动态规划常常出现在各类计算机算法竞赛或者程序员笔试面试中，在数学建模中出现的相对较少，但这个算法的思想在生活中非常实用，会对我们解决实际问题的思维方式有一定启发。

动态规划组成部分：

1. 确定状态：解动态规划的时候需要开一个数组，数组的每个元素需要明确代表什么，类似于确定数学题中X、Y的含义
2. 转移方程：把状态表达成方程
3. 初始条件和边界情况
4. 计算顺序

2. 典型例题

2.1 例1 凑硬币

你有三种硬币，分别面值2元、5元和7元，每种硬币都有足够多，买一本书需要27元，如何用最少的硬币组合起来正好付清，不需要对方找钱

1. 确定状态

   • 最后一步：

     虽然我们不知道最优策略是什么，但是最优策略肯定是有k校硬币，$a_1,a_2,......a_k$加起来面值为27，所以一定存在有最后一枚硬币：$a_k$，除了这枚硬币，前面的面值加起来是$27-a_k$，两个关键点：

     • 我们不关心前面的$k-1$枚硬币是怎么拼出$27-a_k$的(可能有很多种拼法),而且我们现在甚至还不知道$a_k$和$k$是多少，但我们可以确定前面的硬币拼出了$27-a_k$
     • 因为是最优策略，所以拼出$27-a_k$的硬币数一定要最少，否则就不是最优策略

   • 子问题：

     • 最少可以用多少枚硬币拼出$27-a_k$
     • 原问题是最少可以用多少枚硬币可以拼出27
     • 我们将原问题可以转化为一个规模更小的子问题：$27-a_k$

   • 状态：

     我们可以设状态$f(x)=最少用多少枚硬币拼出x$

2. 转移方程

   对于任意$x$
   f [ x ] = m i n { f [ x − 2 ] + 1 , f [ x − 5 ] + 1 , f [ x − 7 ] + 1 } f[x]=min\{f[x-2]+1,f[x-5]+1,f[x-7]+1\} f[x]=min{f[x−2]+1,f[x−5]+1,f[x−7]+1}

3. 初始条件和边界情况

   • 转移方程有两个问题
     • $x-2,x-5,或x-7$小于0怎么办
     • 什么时候停下来
   • 所以：
     • 如果不能拼出Y，那么就定义$f[Y]=$正无穷，例如$f[-1]=f[-2]=f[-3]=\cdots =$正无穷
     • 所以 f [ 1 ] = min ⁡ { f [ − 1 ] + 1 , f [ − 4 ] + 1 , f [ − 6 ] + 1 } = f[1]=\operatorname*{min}\{f[-1]+1,f[-4]+1,f[-6]+1\}= f[1]=min{f[−1]+1,f[−4]+1,f[−6]+1}=正无穷，表示拼不出来
     • 初始条件$f[0]=0$

4. 计算顺序

   • 拼出$x$所需要的最少硬币数： f [ x ] = m i n { f [ x − 2 ] + 1 , f [ x − 5 ] + 1 , f [ x − 7 ] + 1 } f[x]=min\{f[x-2]+1,f[x-5]+1,f[x-7]+1\} f[x]=min{f[x−2]+1,f[x−5]+1,f[x−7]+1}
   • 初始条件：$f[0]=0$
   • 然后计算$f[1],f[2],...,f[x]$

2.2 例2 背包问题

有一个小偷去偷东西，他的背包可以容纳总重量为$W$的物品，现在有$n$件物品，每件物品的重量为$w_i$, 价值为$v_i$ ,求能够放进背包的物品的最大价值。

1. 状态：$dp[i][j]$表示前$i$件物品放入容量为$j$的背包中所获得的最大价值

2. 状态转移方程：对于第$i$件物品，可以选择放或不放

   • 如果不放，那么$dp[i][j]=dp[i-1][j]$

   • 如果放，那么$dp[i][j]=dp[i-1][j-w_i]+{\nu }_i$

   • 选择获得最大价值的情况，即
     $$dp[i][j]=max(dp[i-1][j],dp[i-1][j-w_i]+v_i)$$

3. 初始条件：

   • $dp[0][0]=0$,将前0个物品放入容量为0的背包中能获得的最大价值为0
   • 如果容量为 0,则无法放入任何物品，$dp[i][0]=0$
   • 如果没有物品可选，则无法放入任何物品，$dp[0][j]=0.$

4. 求解顺序：从第一个物品开始，求解到$n$

最终，$dp[n][W]$即为问题的解

python_89">3. python代码实现

3.1 例1

python">def coinChange(n):"""用于计算找零的最少硬币数Args:n (int): 需要找零的金额return:int: 最少硬币数,如果无法找零则返回-1"""dp = [float('inf')]*(n+1)  # 初始化动态规划数组dp[0] = 0  # 金额为0时，最少硬币数为0for i in range(1, n+1):for j in [2, 5, 7]:if i >= j:dp[i] = min(dp[i], dp[i-j]+1)if dp[n] == float('inf'):return -1else:return dp[n]n = int(input("请输入需要找零的金额："))
res = coinChange(n)
print("最少硬币数为：", res)

测试结果：

请输入需要找零的金额：27
最少硬币数为： 5

3.2 例2

python">def knapsack(weights, values, capacity):"""用于求解0-1背包问题的动态规划算法Args:weights (int): 物品的重量列表values (int): 物品的价值列表capacity (int): 背包的容量return:int: 背包能装的最大价值"""n = len(weights)  # 物品的数量dp = [[0 for j in range(capacity+1)] for i in range(n+1)]  # 初始化动态规划数组# 动态规划求解过程for i in range(1, n+1):for j in range(1, capacity+1):if j < weights[i-1]:dp[i][j] = dp[i-1][j]else:dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]]+values[i-1])return dp[n][capacity]w = input("请输入物品的重量列表（用逗号隔开）：")
v = input("请输入物品的价值列表（用逗号隔开）：")
weights = [int(i) for i in w.split(",")]
values = [int(i) for i in v.split(",")]
c = int(input("请输入背包的容量："))
res = knapsack(weights, values, c)
print("背包能装的最大价值为：", res)

输入及输出：

请输入物品的重量列表（用逗号隔开）：1,2,3
请输入物品的价值列表（用逗号隔开）：3,4,5
请输入背包的容量：5
背包能装的最大价值为： 9

请输入物品的重量列表（用逗号隔开）：1,2,3
请输入物品的价值列表（用逗号隔开）：4,5,6
请输入背包的容量：5
背包能装的最大价值为： 11