在Python中找到高效学习方法的程序
假设我们有三个长度相同的列表。它们分别是截止日期(deadlines)、学分(credits)和时长(durations),它们代表课程作业。对于第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)
-
deadlines, duration, credit := jobs[i]
-
如果day + duration − 1 <= deadline,则
- ans := ans,dp(i + 1,day + duration)+ credit的最大值
- 返回ans
-
从main方法返回dp(0, 0)
让我们看以下实现以更好地了解。
更多Python相关文章,请阅读:Python 教程
示例
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