这是我今天期中考试的一个问题，我想知道如何解决它。我只知道用归纳法证明贪心算法。
问题:
你正在做一个编程项目。有n个Java类C1, C2，…(专横的建筑师这么说的)。架构师还说，这些类必须按顺序实现(在完成C1等之前，不允许实现C2)。
每个Java类最多需要8个小时来实现。你每天整整工作8个小时，你不应该在一天结束的时候留下一个未完成的Java类。
为了尽快完成项目，一个策略是每天实现尽可能多的类。证明这个贪婪策略确实是最优策略。(提示:让它成为使用上述策略在前1天内完成的课程总数。
这个问题类似于经典的任务调度情况，系统中的等待时间必须最小化。
设C1, C2，…n、C 投影类和C [1], C [2],…， c[n]它们所需的实现时间。假设你实现了C1 C2…Cn按此顺序。因此，每个类Ck的总时间(等待+实现)将为:
c[1] + c[2] +c + [k ]
因此，我们有总时间:T = n·c [1] + ( n - 1) c·[2] +……n + 2 * c * [ - 1) + c [n ] =总和(k = 1到n )的(n - k + 1) c· [k ]
(对演示表示抱歉-不支持上标，下标和数学方程…)
假设我们的排列中的实现时间不是按升序排序的。因此，我们可以找到两个整数a和b，使得a与 c ()> c (b )。如果我们在T的计算中交换它们，我们有:
T ' = ( n - + 1) c· (b ) + (n - b + 1) c· () +总和( k = 1到n 除了, b )的(n - k + 1) c· [k ]
我们最后计算T - T":
T - T ' = ( n - + 1) ( c () - c (b )) + (n - b + 1) ( c (b ) - c ()) = (b - ) ( c () - c [b ])
根据我们最初的假设(a和 c ()> c [b ]),我们有b - c> 0 () - c (b )> 0,因此 T - 的> 0。
这证明了我们可以通过切换任意一对任务来减少总等待时间，从而使较短的任务先完成。
你的问题陈述是一样的，除了在开始实现一个新类之前，你必须检查你是应该现在开始(如果今天还有足够的时间)还是明天开始。但这里证明的原则在最小化总"等待"时间方面是成立的。
这不是SO的编程问题。问题不在于要求一个编码解决方案，而在于证明贪婪是最优的。这可以用反证法来证明(毫无疑问在期中考试前的课上教过)。
你要做的是计算贪婪所花费的总时间(只有一个解决方案)，并证明一天中的任何交换都会导致更好的解决方案。您可能还需要添加一些内容，说明交换将如何允许u将顺序排列到最优解决方案(如果存在的话)。
我本来打算写一些公式，但我意识到杰夫·莫林已经有了公式，只是方向相反。我认为从贪婪的解决方案开始可能更容易解释，因为"顺序"基本上是由问题定义的，你只能把工作+-哪一天完成。
问题陈述不完整。没有迹象表明任何一节课的时间会少于8小时。既然你不能让任何一节课没有完成，那么你必须在一天开始的时候开始每节课，以确保至少有8小时的时间来学习它。所以如果C2真的花了3个小时，C3真的花了5个小时，那么贪婪算法会允许这两个类在同一天完成。但是C2花了3个小时之后，你必须等到第三天再开始C3以确保你有足够的时间完成因为你不知道C3要花多长时间。
所以限制最终决定了努力将花费n天，每节课1天。所以实现算法是严格顺序的，不是贪心的。
编辑问题中所述的限制
(1)有n个Java类C1, C2，…Cn
(2)这些类必须按顺序实现(在完成C1等之前不允许实现C2)。
(3)每个Java类最多需要8小时来实现但是没有任何少于8小时的课程的估计。
你每天正好工作8小时
(5)你不应该在一天结束的时候离开一个未完成的Java类。
(3,4，&5)假设我花5分钟在第1课上。我现在还剩7小时55分钟。我可以从二班开始吗?不，因为它可能需要8个小时，我必须在8小时工作结束前完成。所以我必须等到第二天才开始上第二节课，以此类推。因此，实施是严格顺序的，需要n天才能完成，每节课1天。
为了使用贪心算法，你需要额外的信息。
(6)您还知道每个类都有一个已知的编码类所需的小时数- h1, h2, h3，…,接下来的。第一课花了h1个小时，第二课花了h2个小时，以此类推。(从第3条开始，每节课不超过8小时)