배낭 문제

무게 제한이 있는 등산객, 자루를 든 도둑, 예산과 프로젝트 목록을 가진 회사는 모두 같은 질문에 맞닥뜨립니다. 한도를 넘지 않으면서 가장 큰 가치를 얻으려면 무엇을 넣어야 할까요? 이것이 배낭 문제이며, 무게가 적당한 크기의 정수일 때 동적 계획법으로 정확하게 풀 수 있습니다.

물건 행과 용량 열로 이루어진 표와 주황색으로 표시된 거꾸로 읽기 경로, 그 옆의 배낭과 크기가 다른 물건들
물건 행과 용량 열로 이루어진 표와 주황색으로 표시된 거꾸로 읽기 경로, 그 옆의 배낭과 크기가 다른 물건들

문제

무게와 가치를 가진 물건 n개와 최대 무게 W까지 담을 수 있는 배낭이 있습니다. 총무게가 W 이하이면서 총가치가 최대가 되도록 물건들을 고르세요. 각 물건은 통째로 넣거나 빼야 하므로 0/1 배낭 문제라고 합니다. 물건이 n개면 가능한 조합은 2ⁿ개이므로, 모두 시도하는 것은 금방 불가능해집니다.

표

best[i][w]를 처음 i개의 물건만 사용해 무게 w에 담을 수 있는 최대 가치라고 합시다. 그러면 best[0][w] = 0이고, 그다음 각 행에는 두 가지 선택이 있습니다. 물건 i를 빼면 best[i − 1][w]가 되고, 그 무게 wᵢ가 들어가면 넣어서 그 가치에 best[i − 1][w − wᵢ]를 더한 값이 됩니다. 둘 중 큰 값이 best[i][w]입니다. 표를 한 행씩 채우면 필요한 두 칸은 항상 이미 준비되어 있습니다.

예제

용량을 7로 하고, 무게가 1, 3, 4, 5이고 가치가 1, 4, 5, 7인 물건 네 개를 생각해 봅시다. 첫 번째 물건만 있으면 1 이상의 모든 용량에서 가치는 1입니다. 두 번째를 추가하면 용량 4에 둘 다 담아 5가 됩니다. 세 번째를 추가하면 용량 7에 물건 2와 3을 담아 9가 됩니다. 무게 5, 가치 7인 네 번째 물건은 용량 6이나 7에서 물건 1과 함께 8을 만들 수 있지만 9가 더 크므로, 오른쪽 아래 칸은 9입니다. 무게 3과 4인 물건을 담으세요.

얼마나 어려울까?

표는 약 n·W 단계가 필요합니다. 빨라 보이지만 W는 수이고, d자리 수는 10의 d제곱만큼 클 수 있으므로 작업량은 입력 길이에 대해 지수적으로 늘어납니다. 배낭 문제는 NP-난해이며, 1972년 리처드 카프가 제시한 21가지 NP-완전 문제 중 하나였습니다. 실제로는 표 방식, 분기 한정법, 좋은 근사 기법이 큰 실제 문제도 잘 처리합니다.

역사와 쓰임

이 이름은 20세기 초 수학자 토비아스 단치히로 거슬러 올라가며, 그의 아들 조지 단치히는 1957년에 이 문제에 대한 고전적인 탐욕 알고리즘을 내놓았습니다. 배낭 문제는 예산 편성과 포트폴리오 선택, 원자재를 최대한 낭비 없이 자르는 일, 화물 적재, 심지어 초기 공개 키 암호에도 등장합니다. 1978년의 머클–헬먼 암호 체계는 배낭 문제를 바탕으로 만들어졌지만 몇 년 뒤 깨졌습니다.

조지 단치그(왼쪽)가 1976년 제럴드 포드 대통령에게 국가과학훈장을 받는 모습. 1957년 단치그는 배낭 문제에 대한 고전적 탐욕 방법을 제시했다. 이름 자체는 아버지 토비아스 단치그에게서 왔다.
조지 단치그(왼쪽)가 1976년 제럴드 포드 대통령에게 국가과학훈장을 받는 모습. 1957년 단치그는 배낭 문제에 대한 고전적 탐욕 방법을 제시했다. 이름 자체는 아버지 토비아스 단치그에게서 왔다.

직접 살펴보기

앱을 열고 표 보기로 바꾼 뒤 단계를 누르세요. 주황색 칸이 채워지는 칸이고, 파란색 칸은 그 칸이 비교하는 두 칸입니다. 바로 위 칸과, 위 행에서 물건의 무게만큼 왼쪽에 있는 칸입니다. 마지막 칸 다음에는 거꾸로 읽기가 오른쪽 아래 모서리에서 주황색으로 올라가고, 담은 물건이 표 아래에 나타납니다.

자주 묻는 질문

0/1, 개수 제한, 무제한 배낭 문제는 무엇이 다른가요?

0/1 버전에서는 각 물건을 최대 한 번 고릅니다. 개수 제한 버전에서는 각 물건의 개수가 정해져 있고, 무제한 버전에서는 몇 개든 고를 수 있습니다. 표는 이들 사이에서 조금만 달라집니다.

배낭 문제에서 탐욕 알고리즘이 맞는 경우가 있나요?

물건을 나눌 수 있는 분할 가능 배낭 문제에서는 무게당 가치가 가장 높은 것부터 고르는 것이 최적입니다. 통째로 넣는 물건에서는 결과가 크게 빗나갈 수 있지만, 탐욕 알고리즘의 결과와 가장 값진 물건 하나 중 더 나은 쪽은 항상 최대 가치의 절반 이상입니다.

표에는 메모리가 얼마나 필요한가요?

전체 표에는 (n + 1)·(W + 1)개의 칸이 필요하며, 물건을 거꾸로 읽어 내려면 이것이 필요합니다. 최대 가치만 필요하다면 W + 1칸짜리 한 행을 오른쪽에서 왼쪽으로 채우는 것으로 충분합니다.

배낭 문제는 부분집합 합 문제와 같은가요?

부분집합 합 문제는 각 물건의 가치가 무게와 같고, 배낭을 정확히 채울 수 있는지를 묻는 특수한 경우입니다. 이것도 NP-완전이며 같은 종류의 표로 풉니다.

시도해 볼 준비가 되셨나요?

브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.

배낭 문제 해 보기