以活动为动态规划解决方案 [英] Dynamic Programming Solution for Activity-selection
问题描述
在 16.1一项活动选择问题 介绍算法的，对于这个问题的动态规划的解决方案给予为
In 16.1 An activity-selection problem of Introduction to Algorithm, the dynamic programming solution for this problem was given as
C [I，J] = 0若S（I，J）为空
c[i, j] = 0 if S(i, j) is empty
C [I，J] =最大{C [I，K] + C [K，J] +1}若S（I，J）不是空
c[i, j] = max { c[i, k] + c[k, j] + 1 } if S(i, j) is not empty
其中， S（I，J）表示集合的活动 A（I）完成后，启动活动和活动 A（J）启动和 C [I，J] 表示一个最佳的尺寸在这之前完成为组解决方案 S（I，J）
where S(i, j) denotes the set of activities that start after activity a(i) finishes and that finish before activity a(j) starts, and c[i, j] denotes the size of an optimal solution for the set S(i, j)
不过，我想到的是另一种简单的解决方案
However, I am thinking of another simpler solution
c[i] = max { c[i - 1], c[f(i)] + 1 }
其中， F（I）给出了兼容与 A（I）并具有最大<活动前strong>完成时间，完成 A（I）启动。
where f(i) gives the activity that is compatible with a(i) and has the max finish time and finishes before a(i) starts.
将这项工作？如果是的话，为什么笔者提供这种复杂的解决方案。如果不是，我缺少什么？
Will this work? If yes, why the author provides this complex solution. If not, what am I missing?
推荐答案
我认为你缺少设计DP解决方案中的许多细节。
I think you are missing many details of designing the dp solution.
- 什么是初始值？
- 什么是基础案例 ？
- 如果存在具有相同的完成时间与（我）兼容的几项活动会发生什么情况？
在设计一个DP的解决方案，所需的属性之一是最优子
When designing a dp solution, one of the properties needed is optimal substructure
的特定状态的计算顺序（例如，c [i]于）是重要的，它只能通过其子问题进行计算。您的解决方案并不能满足这一要求，当你计算C [I]作为，你必须计算机C [J]先用J = F（I），假设J>时我（甚至是J = I + 1），然后你必须计算C [I]计算C [J]之前！所以C [I]取决于C [J]。而c [J]取决于C [I] ==>不正确
The computing order of a particular state (i.e. c[i]) is important, it can only be computed by its subproblems. Your solution does not meet this requirement, as when you computing c[i], you have to computer c[j] first with j = f(i), let's assume j > i (or even j = i+1) , then you have to compute c[i] before computing c[j]! So c[i] depends on c[j] while c[j] depends on c[i] ==> not correct
另一个例子非常相似，这个问题是矩阵链mutiplication
Another example very similar to this question is Matrix chain mutiplication
您可能想看看：）
编辑： 看到你编辑的问题后，那么这里就是我的反应：
After seeing you edit the question, then here's my response:
假设你可以precompute F（I）在合理的时间（这显然可以），您的解决方案是正确的，因为这是贪婪的解决方案作为其他的答案告诉你。
Assuming you can precompute f(i) in reasonable time (which obviously can), your solution is correct as it IS the greedy solution as other answers told you.
为什么它会奏效的原因是很简单的，从字面上讲，
The reason why it works is quite straight forward, literally speaking,
，直到第i个活动，你要么选择活动我（多数民众赞成在C [F（I）] + 1的部分）或不选择它（C [I-1]）的一部分
您可以尝试建立一个正式的证明，以及，一个贪婪的方法的正确性，通常可以用反证法校对（粗略地说，你可以尝试看看为什么就不可能有比大集等C [I-1]如果你不选择我的活动，您选择活动的情况类似我）
You can try to construct a formal proof as well, the correctness of a greedy method can usually be proofed by contradiction (roughly speaking, you can try to see why it is NOT possible to have a larger set other than c[i-1] if you do not choose activity i, similar for the case that you choose activity i)
要回答你为什么笔者展示了DP解决的问题，我认为这是从编程方面的，但我的想法是，用户试图展示两种不同的方式来解决问题，进而在这里说明一个想法：<强>给出其可以通过贪婪方法来解决的一个问题，它也可以通过DP解决，但它是OVERKILLING
To answer your question about why writer demonstrate the dp solution, I think it's out of programming context, but my thought is the user is trying to demonstrate two different ways to solve a problem, and furthermore to illustrate an idea here: given a problem which can be solved by greedy method, it can also be solved by dp but IT IS OVERKILLING.
然后笔者试图帮助读者认识到贪婪和DP之间的区别，因为他们是非常相似的，以一个新的学习。这就是为什么笔者先给DP解决方案，以展现痛苦，那么贪婪的解决方案，最后一个段落贪婪与DP 的<一个href="http://books.google.com.hk/books?id=NLngYyWFl_YC&pg=PA371&lpg=PA371&dq=16.1+An+activity-selection+problem+of+Introduction+to+Algorithm&source=bl&ots=BxWpDy-oK9&sig=K_gic0f17lrmhli5i96eXi0jCjw&hl=zh-TW&sa=X&ei=AhYMU4eUIomDiQfdooGwAQ&ved=0CCkQ6AEwAA#v=onepage&q=16.1%20An%20activity-selection%20problem%20of%20Introduction%20to%20Algorithm&f=false"相对=nofollow>第382
Then the writer try to help the reader to recognize the difference between Greedy and dp as they are quite similar to a new learner. And that's why the writer first give the DP solution to show the pain, then the greedy solution, lastly a paragraph Greedy versus DP in Page 382
所以TL; DR：你的解决方案是正确的，因为它基本上是贪婪的方法来解决这个问题，当然它比在书中给出的DP解决方案要容易得多，因为这是一点书想举例说明。 从书中引述在P.382：......有人可能品性产生一个DP解决一个问题，当一个贪婪的解决方案就足够了，或者人们可能会误以为是一个贪婪的解决方案就足够了...当一个DP解决方案是必需的... 的
这篇关于以活动为动态规划解决方案的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
