배낭 문제 계산기 (0/1·분할 가능)

물건을 쪼갤 수 있느냐가 다릅니다. 0/1 배낭은 물건을 통째로 담거나 아예 안 담거나 둘 중 하나여서 동적계획법으로 풀어야 하고, 분할 가능 배낭은 일부만 잘라 담을 수 있어 「가치/무게」가 큰 것부터 담는 탐욕법이 최적입니다. 그래서 분할 가능 배낭의 답은 언제나 0/1 배낭의 답 이상입니다.

0/1 배낭에서는 그렇지 않습니다. 용량 50에 (무게 10, 가치 60)·(20, 100)·(30, 120)을 주면 비율 순으로 담을 때 앞의 둘만 들어가 160에 그치지만, 뒤의 둘을 담으면 220입니다. 비율이 가장 높은 것을 먼저 담으면 남는 자리가 어중간해져 뒤엣것이 아예 못 들어가기 때문입니다. 쪼갤 수 있을 때만 이 규칙이 최적입니다.

「앞의 i개 물건만 쓰고 용량이 w일 때 담을 수 있는 최대 가치」입니다. 각 칸은 바로 위 칸(그 물건을 안 담는 경우)과 「위쪽에서 그 물건의 무게만큼 왼쪽 칸 + 그 물건의 가치」(담는 경우) 가운데 큰 쪽으로 채웁니다. 오른쪽 맨 아래 칸이 답이며, 거기서 위로 되짚어 값이 바뀌는 지점이 실제로 담은 물건입니다.

0/1 배낭에서는 넣을 수 없습니다. 동적계획법 표가 용량을 0, 1, 2, …로 한 칸씩 훑는 구조라 소수 무게를 놓을 자리가 없기 때문입니다. 단위를 바꿔 정수로 만들어 넣으면 됩니다 — 1.5kg은 무게 15로, 나머지도 100g 단위로 맞추는 식입니다. 분할 가능 배낭은 소수 무게로도 계산합니다.

동적계획법의 계산량이 「물건 수 × 용량」에 비례하기 때문입니다. 물건이 10개여도 용량이 100만이면 칸이 1,000만 개가 됩니다. 용량을 2진수로 적었을 때의 자릿수를 기준으로 보면 지수적으로 늘어나는 셈이라 이를 의사다항 시간이라 부르며, 배낭 문제가 NP-난해인데도 이 표가 실용적으로 돌아가는 이유이자 한계입니다. 이 계산기는 용량 2,000까지 다룹니다.

표를 되짚을 때 값이 바뀐 칸만 「담았다」고 보므로, 값이 같으면 담지 않은 쪽을 고릅니다. 그래서 앞쪽 물건을 덜 쓰는 조합이 나옵니다. 교재의 답과 담은 물건이 달라도 최적값 자체는 같습니다.

전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.