과일이라는 목록과 또 다른 두 개의 값 k와 cap이 있다고 가정합니다. 각 과일[i]에 [c, s, t]의 세 가지 값이 있는 경우 과일 i는 각각 c 비용이 들고 각각의 크기는 s이며 총 t가 있음을 나타냅니다. k는 용량 한도의 과일 바구니 수를 나타냅니다. 다음 제약 조건으로 과일 바구니를 이 순서로 채우고자 합니다.
- 각 바구니에는 같은 종류의 과일만 담을 수 있습니다.
- 각 바구니는 가능한 한 가득 차 있어야 합니다.
- 각 바구니는 가능한 한 저렴해야 합니다.
따라서 최대한 많은 바구니를 채우는 데 필요한 최소 비용을 찾아야 합니다.
따라서 입력이 fruit =[[5, 2, 3],[6, 3, 2],[2, 3, 2]] k =2 cap =4와 같으면 출력은 12가 됩니다. 이 두 개를 사용하면 첫 번째 바구니를 전체 크기 2+2=4로 가득 채울 수 있고 비용은 5+5=10이기 때문에 두 개의 과일 0을 취할 수 있습니다. 그런 다음 과일 2 중 하나가 더 저렴하기 때문에 사용합니다. 비용은 2단위입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- 옵션:=새 목록
- 과일의 각 삼중항(c, s, t)에 대해 다음을 수행합니다.
- t> 0일 때 수행
- fnum :=(cap / s) 및 t의 최소값
- fnum이 0과 같으면
- 루프에서 나오다
- bnum :=t / fnum의 바닥
- 옵션 끝에 삼중항(cap - fnum * s, fnum * c, bnum) 삽입
- t :=t - bnum * fnum
- t> 0일 때 수행
- ans :=0
- 정렬된 옵션 목록의 각 삼중항(left_cap, bcost, bnum)에 대해 다음을 수행합니다.
- bfill :=k 및 bnum의 최소값
- ans :=ans + bcost * bfill
- k :=k - bfill
- k가 0과 같으면
- 루프에서 나오다
- 반환
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def solve(fruits, k, cap): options = [] for c, s, t in fruits: while t > 0: fnum = min(cap // s, t) if fnum == 0: break bnum = t // fnum options.append((cap - fnum * s, fnum * c, bnum)) t -= bnum * fnum ans = 0 for left_cap, bcost, bnum in sorted(options): bfill = min(k, bnum) ans += bcost * bfill k -= bfill if k == 0: break return ans fruits = [[5, 2, 3],[6, 3, 2],[2, 3, 2]] k = 2 cap = 4 print(solve(fruits, k, cap))
입력
[[5, 2, 3],[6, 3, 2],[2, 3, 2]], 2, 4
출력
12