Python 查找高效学习方法的程序

假设我们有三个长度相同的列表。它们是截止日期、学分和持续时间。它们代表课程作业。对于第 i 个作业，deadlines[i] 表示其截止日期，credits[i] 表示其学分，durations[i] 表示完成作业所需的天数。必须完成一个作业才能开始另一个作业。我们必须记住，我们可以在截止日期当天完成作业，并且我们目前处于第 0 天的开始。

因此，如果输入类似于 deadlines = [7, 5, 10]，credits = [8, 7, 10]，durations = [5, 4, 10]，则输出将为 10。

为了解决这个问题，我们将遵循以下步骤：

  • jobs := 对列表 zip(deadlines, durations, credits) 进行排序

  • 定义一个函数 dp()。

    • 如果 i >= jobs 的大小，则

    • 返回 0

  • ans := dp(i + 1, day)

  • deadline, duration, credit := jobs[i]

  • 如果 day + duration - 1 <= deadline，则

    • ans := ans 和 dp(i + 1, day + duration) + credit 的最大值

  • 返回 ans

  • 从主方法返回 dp(0, 0)

让我们看看下面的实现以更好地理解：

示例

 在线演示

class Solution:
   def solve(self, deadlines, credits, durations):
      jobs = sorted(zip(deadlines, durations, credits))
      def dp(i=0, day=0):
         if i >= len(jobs):
            return 0
         ans = dp(i + 1, day)
         deadline, duration, credit = jobs[i]
         if day + duration − 1 <= deadline:
            ans = max(ans, dp(i + 1, day + duration) + credit)
      return ans
return dp()
ob = Solution()
deadlines = [7, 5, 10]
credits = [8, 7, 10]
durations = [5, 4, 10]
print(ob.solve(deadlines, credits, durations))

输入

[7, 5, 10], [8, 7, 10], [5, 4, 10]

输出

10

更新于： 2020年12月15日

76 次查看

开启你的 职业生涯

完成课程后获得认证

开始学习
广告