algorithm - 使用动态规划实现事件选择问题

Question

如何使用动态规划实现事件选择问题(CLRS 练习 16.1-1)。我已经使用 Greedy Method 实现了它，它以线性时间运行(假设数组已经按完成时间排序)。

我知道它构成了最优子结构。

让 $S_{ij}$ 事件集在事件 $a_i$ 完成后开始，并且 在事件 $a_j$ 开始之前完成。如果我们用 $c[i j]$ 表示集合 $S_{ij}$ 的最优解的大小，那么我们将得到递归

$c[i j]  = c[i k] + c[k j] + 1$

Answer 1

我们可以使用动态规划来解决它，方法是保持一个状态，该状态包含有关事件的当前索引的详细信息以及到目前为止我们已经采取的事件的当前完成时间，在事件的每个索引处我们可以使 2决定是否选择一项事件，最后我们需要选择和递归的最大值。 我已经在 C++ 中实现了递归 dp 解决方案:

#include<bits/stdc++.h>

using namespace std;

int n;
int st[1000], en[1000];
int dp[1000][1000];

int solve(int index, int currentFinishTime){
    if(index == n) return 0;
    int v1 = 0, v2 = 0;
    if(dp[index][currentFinishTime] != -1) return dp[index][currentFinishTime];

    //do not choose the current activity
    v1 = solve(index+1, currentFinishTime);

    //try to choose the current activity
    if(st[index] >= currentFinishTime){
        v2 = solve(index+1, en[index]) + 1;
    }
    return dp[index][currentFinishTime] = max(v1, v2);
}

int main(){
    cin >> n;
    for(int i = 0;i < n;i++) cin >> st[i] >> en[i];
    memset(dp, -1, sizeof dp);

    cout << solve(0, 0) << endl;
return 0;
}

http://ideone.com/m0mxx2

在此代码中，dp[index][finish time] 是用于存储结果的 dp 表。