动态规划简介

2019-02-23 本文已影响6人 Jaydu

动态规划（Dynamic Programming， DP）算法采用递归的方式，将较复杂的原问题分解为较为简单的子问题，以求解原问题。

适用情况

一般情况下，我们能将问题抽象出来，并且问题满足无后效性，满足最优子结构，并且能明确的找出状态转移方程的话，就可以使用动态规划。

无后效性：子问题的解一旦确定，就不再改变，不受在这之后、包含它的更大的问题的求解决策影响；
最优子结构：局部最优解能决定全局最优解，即问题能够分解成子问题来解决；
重叠子问题：子问题可能会重复出现，动态规划对每个子问题只解一次，并把解保存起来，方便后续直接调用，通常用一个二维矩阵（表格）来表示不同子问题的答案，以实现更加高效的求解。；
状态转移：每种状态之间目标函数值的变化公式，从状态转移公式即可判断出最优子结构是否存在。

动态规划的实现

对于解空间规模较小的问题，动态规划算法可以利用递归算法实现，相比于单纯的递归算法，动态规划会将子问题的解存储起来，对重叠子问题不需要重新求解，加快了求解速度。

对于解空间规模较大的问题，递归次数过多会导致栈溢出。通常采用非递归算法来实现动态规划算法。

经典问题

斐波那契数列（待补充）

背包问题（待补充）

卡牌游戏问题

小a和小b玩一个游戏，有n张卡牌，每张上面有两个正整数x，y。取一张牌时，个人积分增加x，团队积分增加y。求小a，小b各取若干张牌，使得他们的个人积分相等，且团队积分最大。

用例描述：

输入：
4  # n=4 组数据
3 1  # x, y
2 2
1 4
1 4
输出：10  # 团队积分最大为10

设 $d_{i,j}$ 表示两人从前 $i+1$ 张卡片中进行抽取，且个人积分差 $j$ （a-b）时，团队积分的最大值。因为两人的地位是平等的，我们可以假定 $j\geq 0$ ，因为 $d_{i,j}=d_{i,-j}$ 总是成立的。 $d_{i,j}$ 的取值分情况分析：
（1）当第 $i$ 张卡不需要抽取时， $d_{i,j}=d_{i-1,j}$ ；
（2）当第 $i$ 张卡需要抽取时，要么是a抽取，要么是b抽取，我们假设 $d_{i,j}$ 相对于 $d_{i-1,j'}$ 总是往减小两人积分差的方向变化。因此， $d_{i,j}=\max\{(d_{i-1,j-x_{i-1}} + y_{i-1})\mathbf{1}_{j\geq x_{i-1}},\ (d_{i-1,j+x_{i-1}} + y_{i-1})\mathbf{1}_{j+x_{i-1}\leq m}\}$ 。
因此转移方程为
$d_{i,j}=\max\{d_{i-1,j},\ (d_{i-1,|j-x_{i-1}|} + y_{i-1}),\ (d_{i-1,j+x_{i-1}} + y_{i-1})\mathbf{1}_{j+x_{i-1}\leq m}\}$
其中 $i=0,1,\cdots,n$ ， $j=0,1,\cdots,\max\limits_{i}\{x_i\}$ ，初始边界条件为：
$\begin{align} d_{0,x_{0}}&=y_0\\ \qquad\qquad d_{0,j}&=0\qquad \forall\ j\neq x_0\\ \end{align}$

# 处理输入
n = int(input())
x, y = [], []
for i in range(n):
    _x, _y = list(map(int, input().split()))
    x.append(_x)
    y.append(_y)

# 初始化
mx = max(x)  # 获取最大值，作为差的边界
dp = [[0] * (mx+1) for _ in range(n+1)]  # 初始化dp

# 边界条件
dp[1][x[0]] = max(dp[1][x[0]], y[0])

for i in range(1, n):
    for j in range(mx+1):
        tmp1, tmp2 = 0, 0            
        tmp1 = dp[i-1][abs(j-x[i])] + y[i]
                
        if j + x[i] <= mx:                
            tmp2 = dp[i-1][j+x[i]] + y[i]

        dp[i][j] = max(dp[i-1][j], tmp1, tmp2)  # 三种状态的最高得分
    print(dp[i])

print(dp[n-1][0])
'''
10
'''
print(dp)
'''
[[0, 0, 0, 0], 
[0, 0, 2, 0], 
[0, 3, 2, 0], 
[7, 6, 7, 6], 
[10, 11, 10, 11]]
'''