算法设计笔记-简单的动态规划

一、什么是动态规划

​ 以下引自知乎:

动态规划的本质,是对问题状态的定义状态转移方程的定义

dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems.

​ 在我看来,状态的定义以及状态转移方程的定义,确实是动态规划最核心的两点,但也是让我最为头疼的两点。往往因为无法得到状态转移方程,而对一个动态规划问题无从下手。

​ 动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。但与分治法不同的是,适用于用动态规划法解的问题,经分解得到的子问题往往不是相互独立的,这时候我们就可以通过保存子问题的答案(一般是子问题最优解),而在需要的时候再找出以求得的答案,递推得到原问题的最优解。

动态规划算法适用于解最优化问题。通常可按一下四个步骤设计:

  1. 找出最优解的性质,并刻画其结构的特征
  2. 递归地定义最优值
  3. 以自底向上的方式计算出最优值
  4. 根据计算最优值时得到的信息,构造最优解

步骤很清晰明了,但是想要做到这四步,需要大量的练习来掌握。

这里贴一下知乎上面大神们的回答:

​ 什么是动态规划?动态规划的意义是什么? - 徐凯强 Andy的回答 - 知乎 https://www.zhihu.com/question/23995189/answer/35324479

​ 什么是动态规划?动态规划的意义是什么? - 王勐的回答 - 知乎 https://www.zhihu.com/question/23995189/answer/35429905

二、最优子结构与无后效性

最优子结构:对于多阶段决策问题,如果每一个阶段的最优决策序列的子序列也是最优的,且决策序列具有“无后效性”,就可以将此决策方法理解为最优子结构。

无后效性:动态规划法的最优解通常是由一系列最优决策组成的决策序列,最优子结构就是这些最优决策序列中的一个子序列,对于每个子序列再做最优决策会产生新的最优决策(子)序列,如果某个决策只受当前最优决策子序列的影响,而不受当前决策可能产生的新的最优决策子序列的影响,则可以理解这个最优决策具有无后效性。

就我感觉,无后效性是动态规划中非常重要的一点。

举例:

现在有一个四乘四的网格,左上角有一个棋子,棋子每次只能往下走或者往右走,现在要让棋子走到右下角

假设棋子走到了第二行第三列,记为s(2,3) ,当位于s(2,3)的棋子要进行决策(向右或者向下走)的时候,之前棋子是如何走到s(2,3)这个位置的是不会影响我做这个决策的。之前的决策不会影响了未来的决策(之前和未来相对于现在棋子位于s(2,3)的时刻),这就是无后效性,也就是所谓的“未来与过去无关” 。

有后效性是指,比如说“棋子不能走以及走过的格”,这时,位于s(2,3)的棋子要进行决策是时候,就要考虑之前是如何走到这个位置的,而做出的决策,也会影响未来的决策,这就是有后效性。

三、应用举例

1.背包问题

1.1 0-1背包

1.1.1 问题描述

有N件物品和一个容量为V的背包。第i件物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使价值总和最大。

1.1.2 问题分析

​ 这是最基础的背包问题,也是最基础的动态规划问题。特点是每个物品只有一个,可以选择放或者是不放。

​ 对于这个问题,用子问题定义状态:即F(i,v)表示前i件物体放进容量为v的背包里面我们可得到的最大价值。由此可以得到下面这个动态规划状态转移方程:

​ F(i,v)=max{ F (i-1,v) , F ( i-1 , v-Ci) + Wi } ;

​ 这里,就是取两种状态的最大值,即不选择第i个F (i-1,v)和选择第i个F ( i-1 , v-Ci) + Wi 来作为F(i,v)的最优解。

1.1.3 算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn=10010+10;
int w[maxn];
int c[maxn];
int dp[maxn][maxn];
int n,v;
int solve(){
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++){
for(int j=0;j<=v;j++){
if(j<c[i])
dp[i][j]=dp[i-1][j];
else
dp[i][j]=max(dp[i-1][j],dp[i-1][j-c[i]]+w[i]);
}
}
return dp[n][v];
}
int main(){
cin>>n>>v;
for(int i=1;i<=n;i++){
cin>>w[i]>>c[i];
}
int ans=solve();
cout<<ans<<endl;
}

2.独立任务最优调度问题

2.3 算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn=1010+10;
int a[maxn];
int b[maxn];
int n,v;
int dp[maxn][maxn];
const int inf=0x3f3f3f3f;
int time[maxn];
int solve()
{
int sum=0;
memset(dp,inf,sizeof(dp));
memset(time,inf,sizeof(time));
//cout<<dp[1][1]<<" "<<time[1]<<endl;
sum=sum+a[1];
for(int i=0;i<sum;i++){
dp[1][i]=b[1];
}
dp[1][a[1]]=min(a[1],b[1]);
for(int i=2;i<=n;i++){
sum=sum+a[i];
for(int x=0;x<=sum;x++){
if(x<a[i]){
dp[i][x]=dp[i-1][x]+b[i];
}else{
dp[i][x]=min(dp[i-1][x-a[i]],dp[i-1][x]+b[i]);
}
time[i]=min(time[i],max(x,dp[i][x]));
//cout<<time[i]<<endl;
}
}
return time[n];
}
int main()
{
//int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int j=1;j<=n;j++){
cin>>b[j];
}
int ans=solve();
cout<<ans<<endl;
return 0;
}