使用动态规划实现 Activity 选择概率
Implementing Activity Selection Prob using Dynamic Programming
如何使用动态规划实现 Activity 选择问题(CLRS 练习 16.1-1)。我已经使用 Greedy Method 实现了它,它以线性时间运行(假设数组已经按完成时间排序)。
我知道它构成了最优子结构。
设 $S_{ij}$
在 activity $a_i$
完成后开始的一组活动,并且
在 activity $a_j$
开始之前完成。如果我们表示集合 $S_{ij}$ by $c[i j]$
的最优解的大小,那么我们将得到递归
$c[i j] = c[i k] + c[k j] + 1$
我们可以使用动态规划来解决它,方法是保持一个状态,该状态包含有关 activity 的当前索引和 activity 的当前完成时间的详细信息,我们已经采取了,在 activity 的每个索引处,我们可以做出 2 个决定是否选择 activity,最后我们需要取两个选择和递归中的最大值。
我已经在 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;
}
在此代码中,dp[index][finish time]
是用于存储结果的 dp table。
如何使用动态规划实现 Activity 选择问题(CLRS 练习 16.1-1)。我已经使用 Greedy Method 实现了它,它以线性时间运行(假设数组已经按完成时间排序)。
我知道它构成了最优子结构。
设 $S_{ij}$
在 activity $a_i$
完成后开始的一组活动,并且
在 activity $a_j$
开始之前完成。如果我们表示集合 $S_{ij}$ by $c[i j]$
的最优解的大小,那么我们将得到递归
$c[i j] = c[i k] + c[k j] + 1$
我们可以使用动态规划来解决它,方法是保持一个状态,该状态包含有关 activity 的当前索引和 activity 的当前完成时间的详细信息,我们已经采取了,在 activity 的每个索引处,我们可以做出 2 个决定是否选择 activity,最后我们需要取两个选择和递归中的最大值。 我已经在 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;
}
在此代码中,dp[index][finish time]
是用于存储结果的 dp table。