길이가 같은 세 개의 목록이 있다고 가정합니다. 이는 마감일, 크레딧 및 기간입니다. 그들은 코스 할당을 나타냅니다. i번째 과제의 마감일[i]은 마감일을, credits[i]는 크레딧을, durations[i]는 과제를 완료하는 데 걸리는 일수를 나타냅니다. 다른 과제를 시작하기 전에 한 과제를 완료해야 합니다. 과제를 마감일에 완료할 수 있으며 현재 0일 차 시작 단계에 있다는 점을 염두에 두어야 합니다.
따라서 입력이 마감일 =[7, 5, 10], 크레딧 =[8, 7, 10], 기간 =[5, 4, 10]인 경우 출력은 10이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
작업 :=목록 zip(마감일, 기간, 크레딧) 정렬
-
dp() 함수를 정의합니다.
-
i>=작업 크기인 경우
-
0 반환
-
-
ans :=dp(i + 1, 일)
-
마감일, 기간, 크레딧 :=작업[i]
-
일 + 기간 - 1 <=기한인 경우
-
ans :=ans의 최대값, dp(i + 1, day + duration) + 크레딧
-
-
반환
-
기본 메서드에서 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