0/1 Knapsack Problem
n개의 물건이 있습니다. 물건 i의 무게는 weights[i]이고 가치는 values[i]입니다. 가방에는 최대 capacity의 총 무게까지 담을 수 있습니다. 각 물건은 하나씩만 있으며, 물건을 통째로 넣거나 남겨 두어야 합니다. 담을 수 있는 최대 총가치를 반환하세요.
함수
- weightsinteger-array
- 각 항목의 가중치
- valuesinteger-array
- 각 항목의 값
- capacityinteger
- 가방이 운반할 수 있는 최대 무게
- 반환값integer
- 용량을 초과하지 않는 무게의 항목들로 얻을 수 있는 총 가치의 최댓값
제약 조건
1 ≤ n ≤ 100, 여기서n = weights.length = values.length1 ≤ weights[i] ≤ 10001 ≤ values[i] ≤ 1041 ≤ capacity ≤ 1000
예제
- 입력
- weights = [4, 2, 3, 5]values = [10, 4, 7, 12]capacity = 7
- 출력
- 17
- 설명
- 항목 0과 2의 무게는 4 + 3 = 7이고 가치는 10 + 7 = 17입니다. 가장 가치가 높은 항목(무게 5, 가치 12)을 먼저 넣으면 항목 1만 넣을 수 있어 총 가치는 16입니다.
- 입력
- weights = [5, 4, 3]values = [10, 7, 6]capacity = 7
- 출력
- 13
- 설명
- 항목 1과 2의 무게는 4 + 3 = 7이고 가치는 7 + 6 = 13입니다. 항목 0은 무게 1단위당 2의 가치를 얻어 어떤 항목과도 같지만, 항목 0을 넣고 나면 남은 2단위로는 아무것도 넣을 수 없습니다.
- 입력
- weights = [6, 8]values = [5, 9]capacity = 5
- 출력
- 0
- 설명
- 두 항목 모두 무게가 5보다 커서 아무것도 들어가지 않으며, 빈 가방의 가치는 0입니다.
후속 질문
용량은 10^9까지 커질 수 있고 값의 합은 최대 10^4라고 가정해 봅시다. 표의 인덱스는 무엇을 기준으로 정해야 할까요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
항목 0부터 시작하여 순서대로 결정하세요. 해당 항목을 넣든 그대로 두든, 그다음 항목들에 대해 같은 질문을 마주하게 됩니다. 그 질문에서 어떤 숫자가 바뀌나요?
이후의 최적 값은 두 숫자에만 달려 있습니다. 현재 살펴보는 항목이 무엇인지와 남은 공간이 얼마나 되는지입니다. 항목이 100개이고 용량이 1000이면 이러한 쌍이 약 10^5개 있으므로, 각 쌍의 값을 한 번씩 계산해 저장할 수 있습니다.
0부터
capacity까지 각 용량c에 대해best[c]를 유지하고, 시작할 때는 모두 0으로 설정합니다. 무게가w이고 가치가v인 항목에 대해c를capacity에서w까지 역순으로 순회하면서best[c]와best[c-w] + v중 더 큰 값을 유지합니다. 역순으로 순회하면 항목이 두 번 담기는 것을 방지할 수 있습니다.
풀이
어떤 탐욕적 순서도 통하지 않습니다. 가장 가치가 높은 항목을 먼저 담으면 첫 번째 예제에서 17이 아니라 16을 얻습니다. 항목 i부터 얻을 수 있는 최선의 가치는 i와 남은 용량에만 달려 있으며, 남은 용량은 최대 1000인 정수입니다. 각 쌍마다 테이블 셀 하나를 사용하면 O(n × capacity)가 되고, 용량을 내림차순으로 살펴보면 한 행만으로 충분합니다.
각 항목에 대해 두 가지 선택지를 모두 시도해 보세요
정답이지만 가장 큰 테스트에서는 끝나지 않음
핵심 아이디어
best(i, room)를 i번째 항목부터 시작해 room 단위의 여유 공간에 담을 수 있는 항목들의 최대 가치라고 하자. 마지막 항목을 지나면 값은 0이다. 항목 i를 건너뛰면 best(i+1, room)이 된다. 항목을 담을 때 weights[i] ≤ room이면 values[i] + best(i+1, room-weights[i])이 된다. 둘 중 더 큰 값을 선택한다. 무게 제한에 맞는 모든 패킹은 담기와 건너뛰기 선택의 한 가지 순서이며, 재귀는 모든 경우를 시도한다.
항목 하나가 추가될 때마다 경로의 수는 두 배가 된다. 무게가 각각 10인 항목 100개가 용량 1000인 가방에 모두 들어가는 경우처럼, 항목 100개가 모두 들어가면 경로는 2^100개다.
알고리즘
best(i, room)을 작성하고,i가 마지막 항목을 지나면 0을 반환합니다.skip을best(i+1, room)으로 설정합니다.weights[i] > room이면skip을 반환합니다.- 그렇지 않으면
skip과values[i] + best(i+1, room-weights[i])중 더 큰 값을 반환합니다. best(0, capacity)를 반환합니다.
def knapsack(weights, values, capacity):
n = len(weights)
# The most value items i, i+1, ... can add with room units of weight left
def best(i, room):
if i == n:
return 0
skip = best(i + 1, room)
if weights[i] > room:
return skip
take = values[i] + best(i + 1, room - weights[i])
return max(skip, take)
return best(0, capacity)항목과 용량별로 표 채우기
핵심 아이디어
재귀는 여러 경로를 따라 같은 쌍 (i, room)에 도달합니다. 쌍은 최대 101 × 1001개, 약 10^5개이므로 각각 한 번만 계산하면 됩니다.
best[i][c]를 처음 i개의 항목을 용량 c인 가방에 넣었을 때 얻을 수 있는 최대 가치라고 하겠습니다. 0번째 행은 모두 0입니다. 무게가 w이고 가치가 v인 항목 i-1을 넣지 않으면 best[i-1][c]이고, w ≤ c일 때 넣으면 best[i-1][c-w] + v입니다. 행 i는 행 i-1만 참조하므로 각 항목은 각 칸에 최대 한 번만 반영됩니다.
첫 번째 예제에서 항목 2(무게 3, 가치 7)는 용량 7일 때 best[2][4] + 7 = 17을 만듭니다. 그러면 항목 3은 best[3][2] + 12 = 16만 제시하므로 답은 17로 유지됩니다.
알고리즘
- 행이 n+1개이고 열이 capacity+1개인 표를 만들고, 모든 값을 0으로 설정합니다.
- 1부터 n까지 각 행
i에 대해w = weights[i-1]와v = values[i-1]를 가져옵니다. - 각 용량
c에 대해best[i][c]를best[i-1][c]로 설정합니다. w ≤ c이고best[i-1][c-w] + v가 더 크면, 그 값을 대신 저장합니다.best[n][capacity]를 반환합니다.
def knapsack(weights, values, capacity):
n = len(weights)
# best[i][c]: the most value from the first i items within capacity c
best = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
w, v = weights[i - 1], values[i - 1]
for c in range(capacity + 1):
best[i][c] = best[i - 1][c] # leave item i-1 out
if w <= c and best[i - 1][c - w] + v > best[i][c]:
best[i][c] = best[i - 1][c - w] + v # put it in
return best[n][capacity]한 행, 용량을 내림차순으로 순회
핵심 아이디어
행 i에는 행 i-1만 필요하므로, 행 하나인 best[c]를 유지하고 항목마다 덮어씁니다. 순회 방향에 따라 답이 달라집니다.
c를 작은 값에서 큰 값으로 순회하면 best[c-w]에 현재 항목이 이미 포함되어 있을 수 있습니다. 무게가 3이고 가치가 5인 항목 하나와 용량 6이 주어지면, 용량 3의 가치는 5가 되고, 이어서 용량 6에서 이 값을 읽어 10이 됩니다. 즉, 두 개를 선택한 셈입니다. capacity에서 w까지 큰 값에서 작은 값으로 순회하면, 읽는 셀은 쓰는 셀보다 아래에 있고 나중에 덮어쓰게 되므로 이전 행의 값을 그대로 유지합니다.
항목을 원하는 만큼 선택할 수 있는 경우에는 작은 값에서 큰 값으로 순회하는 것이 올바른 반복문입니다. 여기서 시간 복잡도는 O(n × capacity)로 유지되고 메모리는 한 행으로 줄어듭니다.
알고리즘
- 모두 0인
capacity + 1개의 항목으로best를 만듭니다. - 무게가
w이고 값이v인 각 항목에 대해c를capacity부터w까지 감소시키며 순회합니다. best[c-w] + v가best[c]보다 크면, 그 값을best[c]에 저장합니다.best[capacity]를 반환합니다.
def knapsack(weights, values, capacity):
# best[c]: the most value from the items seen so far within capacity c
best = [0] * (capacity + 1)
for w, v in zip(weights, values):
# Walk the capacities downward so each item goes in at most once
for c in range(capacity, w - 1, -1):
if best[c - w] + v > best[c]:
best[c] = best[c - w] + v
return best[capacity]
함정과 경계 사례
- 한 행 버전에서 용량을 오름차순으로 순회하면 항목을 두 번 담게 됩니다. 무게가 3이고 가치가 5인 항목 하나를 용량이 6인 가방에 넣으면 5가 아니라 10을 얻습니다.
capacity + 1개가 아니라capacity개의 항목으로 행을 구성합니다. 그러면best[capacity-1]를 반환할 때 가방을 정확히 채우는 경우가 누락됩니다. 예를 들어 무게가 1인 항목을 용량이 1인 가방에 넣는 경우가 그렇습니다.- 항목을 음의 무한대로 초기화합니다. 가방을 가득 채울 필요가 없으므로 모든 항목은 0으로 시작해야 합니다. 음의 무한대로 초기화하면 세 번째 예시에서 0이 아니라 음의 무한대를 반환합니다.
- 가방보다 무거운 항목은 건너뛰어야 합니다. 세 번째 예시에서 닫힌 범위
w...capacity는 Swift에서 프로그램을 중단시키고,(w+1):(capacity+1)은 R에서 역방향으로 셉니다.
자주 묻는 질문3
0/1 배낭 문제의 시간 복잡도는 무엇인가요?
이 표 방식은 O(n × capacity) 시간에 실행되며, 항목 100개와 용량 1000일 때 약 10^5단계가 필요하고, 한 행 버전은 O(capacity) 메모리를 사용합니다. 이 상한은 의사 다항식입니다. 즉, 용량의 자릿수가 아니라 용량의 값에 따라 증가합니다. 일반적인 문제는 NP-hard입니다.
0/1 배낭 문제에서 탐욕 알고리즘이 작동하지 않는 이유는 무엇인가요?
탐욕적 규칙은 선택한 항목 때문에 남은 공간을 채울 항목이 없더라도 그 선택을 되돌리지 않습니다. 용량이 7일 때 무게가 5이고 가치가 10인 항목은 가장 좋은 비율로 공동 1위이지만, 무게가 4와 3인 항목을 함께 선택하면 가치는 13입니다. 비율을 기준으로 한 탐욕적 방식은 항목을 나눌 수 있는 분할 배낭 문제에서만 최적입니다.
0/1 배낭 문제에서 어떤 항목이 선택되었는지 어떻게 확인하나요?
전체 표를 유지한 채 best[n][capacity]에서 거꾸로 추적하세요. best[i][c]가 best[i-1][c]와 다르면 항목 i-1이 담긴 것이므로 기록하고 무게만큼 c에서 빼세요. 그렇지 않으면 같은 c를 유지한 채 행 i-1로 이동하세요.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
def knapsack(weights, values, capacity):
# 여기에 코드를 작성하세요테스트 #1
테스트 #2
테스트 #3
인자들
weights = [4, 2, 3, 5] values = [10, 4, 7, 12] capacity = 7
예상 출력
17