具有时间约束的任务的贪婪算法

Question

这是我今天期中考试的一个问题，我想知道如何解决这个问题。我只知道用归纳法证明贪婪算法。

问题：

你在做一个编程项目。有n个Java类C1、C2、.、Cn (专横的架构师这么说)。架构师还说，这些类必须按顺序实现(在完成C2之前不允许实现C1等等)。

每个Java类最多需要8个小时来实现。您每天工作整整8个小时，不应该在一天结束时留下一个Java类未完成。

为了尽快完成项目，一种策略是每天尽可能多地实现类。证明了这个贪婪策略确实是最优的。(提示:使用上述策略在第一I天完成的类总数)。如果ti不少于使用任何其他策略的第一个i天完成的课程总数，则策略始终保持领先)

Answer 1

问题陈述是不完整的。没有任何迹象表明任何课程将花费少于8小时。因为你不能留下任何未完成的课程，那么你必须在一天开始的时候开始每堂课，以确保至少有8个小时的时间来完成它。因此，如果C2真的需要3个小时，而C3真的需要5个小时，那么一个贪婪的算法将允许两个类在同一天完成。但是在C2花费了3个小时之后，您必须等到第3天才启动C3，以确保您有足够的时间完成，因为您不知道C3需要多长时间。

因此，这些限制最终决定了每堂课要花费n天，1天的时间。因此，实现算法是严格顺序的，而不是贪婪的。

编辑在problem.中声明的限制

(1)有n个Java类C1、C2、.、Cn

(2)这些类必须按顺序实现(在完成C2之前不允许实现C1等等)。

(3)每个Java类最多需要8个小时来实现

但是，对于任何少于8小时的课程，我们并没有估计。

(4)你一天工作整整8个小时

(5)您不应该在一天结束时留下一个Java类未完成。

这个(3,4，& 5)的要点是让我们假设我在第1课上工作了5分钟。我现在还有7小时55分钟。我可以从二班开始吗？不，因为它可能需要8个小时，我必须在我的8小时结束之前完成。所以我必须等到第二天才开始上课，等等。因此，实现是严格顺序的，需要n天才能完成，每堂课1天。

为了使用贪婪的算法，您需要更多的信息.

(6)您还知道，每个类都有编写该类所需的已知时间-- h1、h2、h3、.、hn。因此，1级需要h1小时，2类需要h2小时，等等。(如第3项所示，上课时间不得超过8小时)

Answer 2

这不是一个编程问题。问题不在于要求一个编码解决方案，而在于它证明贪婪是最佳的。这可以通过矛盾的证据来完成(毫无疑问，期中前在课堂上教过)。

你要做的是计算贪婪所花费的总时间(只有一个解决方案)，并证明白天的任何掉期都会带来更好的解决方案。您可能还必须添加一些内容，其中提到了交换如何允许您将顺序更改为最优解，如果存在的话。

我本来要写一些公式，但我意识到杰夫·莫林已经有了方程，只是在相反的方向上。我认为从贪婪的解决方案开始可能更容易解释，因为“有序”基本上是由问题定义的，而且您只能转移工作+-哪一天它完成了。