使用动态编程实现活动选择概率

debugcn 发表于 Dev

用户名

如何使用动态编程实现活动选择问题（CLRS练习16.1-1）。我已经使用贪婪方法实现了它，它在线性时间内运行（假设数组已经按完成时间排序了）。

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

让 $S_{ij}$ 在活动 $a_i$ 结束之后开始并且在活动 $a_j$ 开始之前结束的活动集。如果我们表示该集合的最优解的大小，$S_{ij}$ by $c[i j]$则将有递归

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

uSeemSurprised

我们可以通过使用动态编程来解决此问题，方法是保持一个状态，该状态包含我们迄今为止已进行的活动的当前索引和活动的当前完成时间的详细信息，在活动的每个索引处，我们可以做出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表用于存储结果。

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。