Coding►Algorithm►DP

《算法导论》动态规划，贪心算法与分治法

  1. 1. ★动态规划
    1. 1.1. ◇设计步骤
    2. 1.2. ◇最优子结构（设计步骤1、2）
    3. 1.3. ◇重叠子问题（设计步骤3）
    4. 1.4. ◇重新构造一个最优解（设计步骤4）
    5. 1.5. ◇一种变形：做备忘录
  2. 2. ★贪心算法
    1. 2.1. ◇贪心选择性质
  3. 3. ★分治法
  4. 4. ★一个实例：活动选择问题

★动态规划

◇设计步骤

  1. 描述最优解的结构
  2. 递归定义最优解的值
  3. 按自底向上的方式计算最优解的值
  4. 由计算出的结果构造一个最优解

◇最优子结构（设计步骤1、2）

如果一个问题的最优解中包含了子问题的最优解，则该问题具有最优子结构。

◇重叠子问题（设计步骤3）

当一个递归算法不断地调用同一问题时，则该最优问题包含重叠子问题。

动态规划算法总是充分利用重叠子问题，即通过每个子问题只解一次，把解保存在一个在需要时就可以查看的表中。

适合用分治法解决的问题旺旺在递归的每一步都产生全新的子问题，且对递归树中重复出现的每个子问题都要重复解一次。

◇重新构造一个最优解（设计步骤4）

每一个子问题所做的选择保存在一个表格中，这样在需要时，就不必根据已经储存下来的代价信息来重构这方面的信息了。

◇一种变形：做备忘录

与原形不同的是，备忘录方法采用的是自顶向下的策略。通过备忘原问题的自然但低效的递归算法，维护一个记录了子问题解的表，但有关填表动作的控制结构更像递归算法。

如果所有的子问题都至少要被计算一次，则一个自底向上的动态规划算法通常要比一个自顶向下的做备忘录的算法好出一个参数因子，因为前者无需递归的代价。

如果子问题空间中的某些子问题根本没有必要求解，做备忘录方法有着只解那些肯定要求解的子问题的优点。

★贪心算法

◇贪心选择性质

一个全局的最优解可以通过局部最优（贪心）选择来达到。

贪心策略通畅是自顶向下地做的，一个一个地作出贪心选择，不断地将给定的问题实例约为更小的问题。

★分治法

适合用分治法解决的问题旺旺在递归的每一步都产生全新的子问题，且对递归树中重复出现的每个子问题都要重复解一次。

★一个实例：活动选择问题

给定一组活动的开始时间和结束时间，然后他们都需要使用到一个资源，这个资源每次只有一个活动可以用，要求求出一个最大的相互兼容的活动子集。

首先定义了一个集合Sij = {ak∈ S :fi ≤ sk < fk ≤ sj} , 其中S就是所有活动的集合，fi是活动ai的完成时间si是活动ai的开始时间。

找出递归式：

完整递归定义

关于该问题动态规划算法，发现习题答案和很多网友给出的伪代码或实现都有问题，算法中居然没有对s[],f[]的使用，怎么可能得出结果！

以下是动态规划和贪心算法（递归和迭代两个版本）的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
59
60
61
62
63
64
65
66
#include "stdafx.h"
#include <iostream>
using namespace std;
const int size = 13; // 11个活动，加上虚构活动a0和an+1
// 动态规划：构造最优解
void recursive_activity_selector(int s[], int f[], int c[], int p[][size], int num)
{
truefor (int i = 0; i < num; ++i)
truetruefor (int j = 1; j < num; ++j)
truetruetrueif (i >= j)
truetruetruetruec[i][j] = 0;
truetruetrueelse
truetruetruetruefor (int k = i + 1; k < j; k++)
truetruetruetruetrueif (f[i] <= s[k] && f[k] <= s[j]) // 习题答案和很多网友给出的伪代码或实现都没有这句，显然有问题
truetruetruetruetruetrueif (c[i][j] < c[i][k] + c[k][j] + 1) {
truetruetruetruetruetruetruec[i][j] = c[i][k] + c[k][j] + 1;
truetruetruetruetruetruetruep[i][j] = k;
truetruetruetruetruetrue}
}
// 动态规划：输出最优解
void print(int i, int j, int p[][size])
{
trueint k = 0;
trueif (p[i][j] == 0)
truetruereturn ;
truecout << p[i][j] << " ";
trueprint(i, p[i][j], p);
trueprint(p[i][j], j, p);
}
// 贪心算法：递归版本
void recursive_activity_selector(int s[], int f[], int i, int n, int c[][size])
{
trueint m = i + 1;
truewhile (m <= n && s[m] < f[i])
truetrue++m;
trueif (m < n) {
truetruec[i][n] = m;
truetruerecursive_activity_selector(s, f, m, n, c);
true}
}
// 贪心算法：迭代版本
void greedy_activity_selector(int s[], int f[], int i, int n, int c[][size])
{
truefor (int m = 1; m < n; ++m)
truetrueif (s[m] >= f[i]) {
truetruetruec[i][n] = m;
truetruetruei = m;
truetrue}
}
int main()
{
trueint s[size] = {65535,1,3,0,5,3,5,6,8,8,2,12,65535}; // 开始时间
trueint f[size] = {0,4,5,6,7,8,9,10,11,12,13,14,0}; // 结束时间
trueint c[size][size] = {0};
trueint p[size][size] = {0};
truerecursive_activity_selector(s, f, c, p, size);
truefor (int i = 0; i < size; i++) {
truetruefor (int j = 0; j < size; j++)
truetruetruecout << p[i][j] << " ";
truetruecout << endl;
true}
truecout << endl;
trueprint(0, size - 1, p);
truesystem("pause");
truereturn 0;
}