使用动态规划实现活动选择问题

Question

如何使用动态规划实现活动选择问题（CLRS练习16.1-1）。我已经使用贪心算法实现了它，假设数组已经按完成时间排序，则运行时间为线性时间。

我知道它具有最优子结构。

令$S_{ij}$表示在活动$a_i$完成后开始并在活动$a_j$开始之前完成的活动集。如果我们用$c[i j]$表示集合$S_{ij}$的最优解大小，则我们将得到以下递推式。

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

- user5328749

---

你有什么问题？ - leeor

我的问题是如何在任何编程语言（比如Python）中实现这段代码。我的意思是如何选择特定的任务并将列表分成部分，然后递归地解决它们并合并结果。 - user5328749

Answer 1

我们可以使用动态规划来解决这个问题，通过保持一个状态，其中包含当前活动索引和到目前为止我们已经选择的活动的当前完成时间的详细信息，在每个活动索引处，我们可以做出两个决策：选择一个活动或不选择任何活动，最后我们需要取两个选择中的最大值并进行递归。我已经在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][结束时间]是用于存储结果的 dp 表。

- uSeemSurprised

---

你能在回答中包含代码吗？这可能会有所帮助，最好在帖子中包含外部内容（特别是如果它是你自己的），因为如果链接消失，你的帖子将失去一些价值。 - Artjom B.

你能再多解释一下吗？我在努力理解，但是有点困难。谢谢！ - denyzprahy

@Denis Cappelini 你具体不明白哪一部分？ - uSeemSurprised

@Denis Cappelini，这是必须的记忆化技术，你应该搜索并了解它。基本上，它存储状态答案，每当我们有相同的状态需要计算时，我们只需使用已存储的结果，而不是重新计算。如果您删除它，则算法将变成指数级别而不是多项式级别。尝试使用大输入运行此代码，它会工作，但如果您删除dp矩阵并再次尝试，则无法正常工作。 - uSeemSurprised

@Denis Cappelini 我们尝试在dp解决方案中做出决策，即选择某些对象或不选择，然后选择给出最佳答案的对象。将当前完成时间传递为0是基本条件，即尚未选择任何活动且完成时间为0。 - uSeemSurprised