Fractional Knapsack
n개의 아이템이 있습니다. 아이템 i의 가치는 values[i]이고 무게는 weights[i]입니다. 가방에 담을 수 있는 총무게는 최대 capacity이며, 아이템의 일부만 가져갈 수도 있습니다. 무게가 w인 아이템 i의 일부 조각의 가치는 values[i] × w / weights[i]입니다.
가방에 담을 수 있는 최대 총가치를 구하고 소수점 이하를 버려 정수로 반환하는 fractionalKnapsack 함수를 작성하세요.
함수
- valuesinteger-array
- 각 항목의 값
- weightsinteger-array
- 각 항목의 무게
- capacityinteger
- 가방이 담을 수 있는 최대 무게
- 반환값integer
- 가방에 들어가는 총 가치 중 가장 큰 값(내림 처리)
제약 조건
1 ≤ n ≤ 5000, 여기서n = values.length = weights.length1 ≤ values[i], weights[i] ≤ 1041 ≤ capacity ≤ 108
예제
- 입력
- values = [40, 90, 30, 50]weights = [8, 30, 5, 20]capacity = 40
- 출력
- 151
- 설명
- 무게 단위당 아이템의 가치는 5, 3, 6, 2.5입니다. 아이템 2와 0을 전부 담으면 가치가 70이고, 27의 여유가 남습니다. 아이템 1의 30단위 중 27단위를 더하면 81이 되어 총 151입니다.
- 입력
- values = [10, 7]weights = [4, 3]capacity = 5
- 출력
- 12
- 설명
- 항목 0은 단위당 가치가 2.5이고 항목 1은 약 2.33이므로, 항목 0은 전부 넣어 10을 얻습니다. 항목 1의 3개 단위 중 하나는
7 / 3을 더하고, 12와 3분의 1은 내림하여 12가 됩니다.
- 입력
- values = [5, 8]weights = [2, 3]capacity = 100
- 출력
- 13
- 설명
- 두 물건 모두 여유 있게 들어가므로 전부 가져갑니다: 5 + 8 = 13.
후속 질문
모든 항목을 정렬하지 않고 O(n) 시간 안에 답을 찾을 수 있나요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
가방에 무게를 한 단위 더 넣을 공간이 있다면, 어떤 항목에서 그 무게만큼 가져오시겠어요?
무게 단위당 가치는 무게당 가치가 가장 높은 물품에서 가장 큽니다. 가장 밀도가 높은 물품부터 가방을 채우고, 마지막으로 넣는 물품만 잘라 넣습니다.
밀도가 높은 항목부터 정렬합니다. 나눗셈을 하지 않도록
values[a] × weights[b]와values[b] × weights[a]를 비교하세요. 들어가는 동안은 항목을 통째로 담고, 가방을 채우는 항목에는 정수 나눗셈으로values[i] × room / weights[i]를 더하세요.
풀이
물건을 잘라 담을 수 있으므로 이 문제는 0/1 배낭 문제와 달리 그리디 문제입니다. 남은 물건 중 단위 무게당 가치가 가장 높은 물건에서 무게를 1단위씩 채워야 합니다. 단위 무게당 가치에 따라 정렬한 뒤 순서대로 배낭을 채우세요. 단위 무게당 가치는 교차 곱셈으로 비교하고, 잘라 담는 물건에만 내림을 적용하면 분수를 저장할 일이 없습니다.
매 라운드마다 밀도가 가장 높은 항목을 선택합니다
정답이지만 가장 큰 테스트에서는 끝나지 않음
핵심 아이디어
가장 밀도가 높은 물건부터 가방을 채우세요. 들어가면 물건 전체를 담고, 그렇지 않으면 가방을 채우는 만큼만 담은 뒤 멈추세요. 모든 물건을 훑어 가장 밀도가 높은 미사용 물건을 찾을 때는 나누는 대신 values[i] × weights[j]와 values[j] × weights[i]를 비교하세요. 무게가 양수라면 같은 검사이며, 두 곱은 모두 10^8 이하입니다.
밀도가 높은 물건부터 담는 것이 최선입니다. 더 밀도가 높은 물건이 아직 전부 들어가지 않았는데 덜 밀도가 높은 물건의 일부 무게가 실려 있다면, 그 무게만큼 더 밀도가 높은 물건으로 바꿔도 가치는 낮아지지 않습니다. 계속 바꾸면 밀도가 높은 물건부터 담은 상태에 도달합니다.
최대 n번의 각 라운드에서 미사용 물건을 훑습니다. n = 5000일 때 비교 횟수는 약 n²/2 = 12.5 million입니다.
알고리즘
- 모든 항목을 미사용으로 표시하고
room = capacity및total = 0으로 설정합니다. - 수용 공간이 남아 있는 동안 미사용 항목을 훑어 밀도가 가장 높은 항목을 찾습니다. 밀도는 교차 곱셈으로 비교합니다.
- 남은 항목이 없으면 중단합니다. 그렇지 않으면 해당 항목을 사용한 것으로 표시합니다.
- 들어맞으면 해당 항목의 값을
total에 더하고 무게만큼room에서 뺍니다. 들어맞지 않으면 정수 나눗셈으로values[i] × room / weights[i]를 더한 다음 중단합니다. total을 반환합니다.
def fractionalKnapsack(values, weights, capacity):
n = len(values)
used = [False] * n
total = 0
room = capacity
while room > 0:
best = -1
for i in range(n):
# i is denser than best: values[i] / weights[i] > values[best] / weights[best], cross-multiplied
if not used[i] and (best == -1 or values[i] * weights[best] > values[best] * weights[i]):
best = i
if best == -1:
break # every item is already in the bag
used[best] = True
if weights[best] <= room:
total += values[best]
room -= weights[best]
else:
total += values[best] * room // weights[best] # the part that fits, rounded down
room = 0
return total무게당 가치로 정렬
핵심 아이디어
스캔은 밀도가 가장 높은 항목을 계속해서 찾지만, 라운드가 바뀌어도 순서는 변하지 않습니다. 교차 곱셈 비교를 사용해 항목을 밀도가 높은 순서대로 한 번만 정렬하세요. 밀도가 같은 항목은 단위당 가치가 같으므로 어느 순서로든 놓을 수 있습니다.
들어가는 동안 항목을 통째로 가져가세요. 들어가지 않는 첫 번째 항목만 자르면 됩니다. 이 항목은 values[i] × room / weights[i]만큼 더하며, 정수 나눗셈은 소수 부분을 버립니다. 그 앞의 항목은 모두 정수 단위이므로 이 항 하나만 반올림하면 정확한 답을 얻습니다. 정렬에는 O(n log n)이 걸리고, 순회에는 O(n)이 걸립니다.
알고리즘
- 항목 인덱스 목록을 만들고, 교차 곱 비교를 사용해 밀도가 높은 순서대로 정렬합니다.
room = capacity와total = 0을 설정합니다.- 해당 순서대로 각 항목에 대해
weights[i] ≤ room이면 값을 더하고 해당 항목의 무게만큼room에서 뺍니다. - 그렇지 않으면 정수 나눗셈으로
values[i] × room / weights[i]을 더하고 멈춥니다. total을 반환합니다.
from functools import cmp_to_key
def fractionalKnapsack(values, weights, capacity):
# a goes before b when values[a] / weights[a] > values[b] / weights[b],
# tested as values[a] * weights[b] > values[b] * weights[a] to stay in whole numbers.
def denser_first(a, b):
return values[b] * weights[a] - values[a] * weights[b]
order = sorted(range(len(values)), key=cmp_to_key(denser_first))
total = 0
room = capacity
for i in order:
if weights[i] <= room:
total += values[i] # the whole item fits
room -= weights[i]
else:
total += values[i] * room // weights[i] # the part that fits, rounded down
break
return total
함정과 경계 사례
- 가치나 무게만으로 정렬하기. 첫 번째 예제에서 가치가 90인 물건은 밀도 순위가 세 번째일 뿐입니다. 이 물건을 먼저 담으면 가치가 50인 물건의 절반을 담을 공간이 남아, 151이 아니라 115를 얻습니다.
- 곱하기 전에 나누기. 가치가 13, 무게가 7이고 남은 용량이 3일 때, 정수 연산에서
13 / 7 * 3은 3이 되지만,13 * 3 / 7은 올바른 값인 5를 반환합니다. - 매번 물건을 자를 수 있다고 예상하기. 세 번째 예제에서는 모든 물건이 들어가며, 답은 모든 가치의 합인 13입니다.
자주 묻는 질문3
분할 배낭 문제의 시간 복잡도는 얼마인가요?
무게당 가치로 항목을 정렬하는 데 O(n log n)이 들고 한 번 순회하며 채우므로, 전체 시간 복잡도는 O(n log n)이고 순서를 저장하는 데 O(n)의 공간이 필요합니다. 매 라운드마다 밀도가 가장 높은 항목을 검색하면 O(n²)이 듭니다.
분할 배낭 문제에서는 탐욕 알고리즘이 작동하지만 0/1 배낭 문제에서는 작동하지 않는 이유는 무엇인가요?
분할을 허용하면 밀도가 낮은 물건의 무게를 밀도가 더 높은 물건으로 바꿀 수 있습니다. 분할을 허용하지 않으면 밀도가 높은 물건을 담고 난 뒤 남은 공간을 다른 물건으로 채우지 못할 수 있습니다. 가치가 8, 11, 15이고 무게가 2, 3, 4이며 용량이 7일 때, 밀도가 높은 순서대로 선택하면 무게 2와 4인 물건을 담아 가치 23을 얻지만, 무게 3과 4인 물건을 담으면 가치 26을 얻습니다. 0/1 버전에는 동적 계획법이 필요합니다.
부동 소수점 숫자 없이 분할 배낭 문제를 어떻게 해결하나요?
가중치가 양수일 때 a / b > c / d는 a × d > c × b와 같은 비교이므로, 교차 곱셈으로 밀도를 비교합니다. 최적의 값은 정수와 분수 하나의 합이며, 잘라서 담는 항목의 경우 values[i] × room / weights[i]입니다. 따라서 정수 나눗셈 한 번으로 내림한 답을 정확히 구할 수 있습니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
def fractionalKnapsack(values, weights, capacity):
# 여기에 코드를 작성하세요테스트 #1
테스트 #2
테스트 #3
인자들
values = [40, 90, 30, 50] weights = [8, 30, 5, 20] capacity = 40
예상 출력
151