D일 이내에 한 항구에서 다른 항구로 배송될 패키지가 컨베이어 벨트에 있다고 가정합니다. 여기에서 컨베이어 벨트의 i번째 패키지는 weight[i]의 무게를 갖습니다. 매일 우리는 벨트에 소포를 싣고 배를 싣습니다. 우리는 선박의 최대 중량 용량보다 더 많은 중량을 적재하지 않을 것입니다. 컨베이어 벨트에 있는 모든 패키지가 D일 이내에 배송되도록 하는 선박의 최소 중량 용량을 찾아야 합니다. 따라서 입력이 [3,2,2,4,1,4]이고 D =3이면 출력은 6이 됩니다. 6의 배송 용량은 3일 안에 모든 패키지를 배송하는 최소값이기 때문입니다. -
-
1일차:3, 2
-
2일차:2, 4
-
3일차:1, 4
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
재귀 함수 solve()를 정의합니다. 이것은 weights 배열, maxWeight 및 ships 배열을 사용합니다. 이것은 다음과 같이 작동합니다. -
-
인덱스 :=0
-
for i in range 0 to length of ships array
-
배송[i] :=0
-
동안 index <무게와 선박의 길이[i] + weights[index] <=maxWeight
-
배송[i] :=배송[i] + 무게[색인]
-
인덱스 1 증가
-
-
-
index =가중치의 길이인 경우 true를 반환하고, 그렇지 않으면 false를 반환
-
주요 방법은 다음과 같이 작동합니다.
-
ships :=D와 같은 크기의 배열, 0으로 채움
-
maxWeight :=가중치의 최대값
-
low :=maxWeight, high :=maxWeight + weight 배열의 길이 + 1
-
낮음 <높음
동안-
중간 :=낮음 + (높음 - 낮음)/2
-
solve(weights, mid, ships)가 true이면 high :=mid, 그렇지 않으면 low :=mid + 1
-
-
높은 수익
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
class Solution(object): def shipWithinDays(self, weights, D): ships = [0 for i in range(D)] max_w = max(weights) low = max_w high = max_w * len(weights)+1 while low<high: mid = low + (high-low)//2 if self.solve(weights,mid,ships): high = mid else: low = mid+1 return high def solve(self,weights,max_w,ships): index = 0 for i in range(len(ships)): ships[i] = 0 while index < len(weights) and ships[i]+weights[index]<= max_w: ships[i] += weights[index] index+=1 return index == len(weights) ob = Solution() print(ob.shipWithinDays([3,2,2,4,1,4],3))
입력
[3,2,2,4,1,4] 3
출력
6