資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究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 次檢視
廣告