算法分析(动态规划)

基本概念

动态规划的过程:每次决策依赖于当前状态,又随即引起状态的转移。一个决策序列就是在变化的状态中产生的。所以,这种多阶段最优化决策解决问题的过程就称为动态规划。

使用动态规划技术的必要条件

一个最优决策序列的任何子序列本身一定是相对于子序列的初始和结束状态的最优决策序列。

经典例子分析

最长公共子序列

题目:设X和Y是两个序列,其中
X=
Z=
如果Z中元素所有元素都在X中存在,且先后顺序不变,那么Z是X的子序列。Z含有的元素个数,称为子序列长度。
那么给定序列
X=
Y=
求X和Y的最长公共子序列。
下面是用C++实现的代码

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
53
54
55
56
57
58
#include<iostream>
#include<vector>
using namespace std;

int main()
{

vector<char> vec1;
vector<char> vec2;
char ch1, ch2;
int c[100][100], b[100][100], i, j;
while(1)
{
cin >> ch1;
if(ch1 == '0') break;
vec1.push_back(ch1);
}
while(1)
{
cin >> ch2;
if(ch2 == '0') break;
vec2.push_back(ch2);
}

vector<char>::iterator it1 = vec1.begin();
vector<char>::iterator it2 = vec2.begin();

for(i = 0; i <= vec1.size(); i++)
{
c[i][0] = 0;
}
for(i = 0; i <= vec2.size(); i++)
{
c[0][i] = 0;
}
for(i = 1, it1 = vec1.begin(); it1 != vec1.end(); it1++, i++)
{
for(j = 1, it2 = vec2.begin(); it2 != vec2.end(); it2++, j++)
{
if(*it1 == *it2)
{
c[i][j] = c[i-1][j-1] + 1;
b[i][j] = 1;
}
else if(c[i-1][j] >= c[i][j-1])
{
c[i][j] = c[i-1][j];
b[i][j] = 2;
}
else
{
c[i][j] = c[i][j-1];
b[i][j] = 3;
}
}
}
cout << c[vec1.size()][vec2.size()] << endl;
return 0;
}

背包问题

背包问题(Knapsack Problem)是一个著名的NP难问题。
题目:一个旅行者准备随身携带一个背包。可以放入背包的物品有n种,物品j的重量和价值分别为wj,vj,j=1,2,…,n。如果背包的最大重量限制为b,怎样选择放入背包的物品以使得背包的价值最大?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
#include<vector>
using namespace std;

int main()
{

vector<float> weight;
vector<float> value;
float w, v;
while(1)
{
cin >> w >> v;
if(w == 0 && v == 0)
{
break;
}
weight.push_back(w);
value.push_back(v);
}