jobs[i]가 i번째 작업을 완료하는 데 필요한 시간을 나타내는 배열이 있다고 가정합니다. 우리는 또한 그들에게 우리가 작업을 할당할 수 있는 또 다른 값 k가 있습니다. 각 작업은 정확히 한 작업자에게 할당되어야 합니다. 그리고 노동자의 노동 시간은 그들에게 할당된 모든 작업을 완료하는 데 걸리는 총 시간입니다. 우리는 모든 과제의 가능한 최소 최대 작업 시간을 찾아야 합니다.
따라서 입력이 jobs =[2,1,3,8,5], k =2와 같으면 출력은 10이 됩니다. 왜냐하면 다음과 같은 작업을 할당할 수 있기 때문입니다.
-
작업자1:2 + 5 + 3 =10
-
작업자2:1 + 8 =9
따라서 최대 시간은 10입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
목록 작업을 역순으로 정렬
-
assign :=처음 k개의 작업 목록
-
작업 :=남은 작업 목록
-
dp() 함수를 정의합니다. 이렇게 하면 할당됩니다.
-
i가 작업의 크기와 같으면
-
할당의 최대값 반환
-
-
ans :=무한대
-
0 ~ k - 1 범위의 x에 대해 수행
-
assign :=assign의 새 목록
-
할당[x] :=할당[x] + 작업[i]
-
ans :=ans 및 dp(i+1, assign)의 최소값
-
할당[x] :=할당[x] - 작업[i]
-
-
반환
-
기본 메서드에서 dp(0, assign)
를 반환합니다.
예시
더 나은 이해를 위해 다음 구현을 살펴보겠습니다.
def solve(jobs, k):
jobs.sort(reverse=True)
assign = tuple(jobs[:k])
jobs = jobs[k:]
def dp(i, assign):
if i == len(jobs):
return max(assign)
ans = float('inf')
for x in range(k):
assign = list(assign)
assign[x] += jobs[i]
ans = min(ans, dp(i+1, tuple(assign)))
assign[x] -= jobs[i]
return ans
return dp(0, assign)
jobs = [2,1,3,8,5]
k = 2
print(solve(jobs, k)) 입력
[2,1,3,8,5], 2
출력
10