배낭 문제
무게 제한이 있는 등산객, 자루를 든 도둑, 예산과 프로젝트 목록을 가진 회사는 모두 같은 질문에 맞닥뜨립니다. 한도를 넘지 않으면서 가장 큰 가치를 얻으려면 무엇을 넣어야 할까요? 이것이 배낭 문제이며, 무게가 적당한 크기의 정수일 때 동적 계획법으로 정확하게 풀 수 있습니다.
문제
무게와 가치를 가진 물건 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년의 머클–헬먼 암호 체계는 배낭 문제를 바탕으로 만들어졌지만 몇 년 뒤 깨졌습니다.
직접 살펴보기
앱을 열고 표 보기로 바꾼 뒤 단계를 누르세요. 주황색 칸이 채워지는 칸이고, 파란색 칸은 그 칸이 비교하는 두 칸입니다. 바로 위 칸과, 위 행에서 물건의 무게만큼 왼쪽에 있는 칸입니다. 마지막 칸 다음에는 거꾸로 읽기가 오른쪽 아래 모서리에서 주황색으로 올라가고, 담은 물건이 표 아래에 나타납니다.
자주 묻는 질문
0/1, 개수 제한, 무제한 배낭 문제는 무엇이 다른가요?
0/1 버전에서는 각 물건을 최대 한 번 고릅니다. 개수 제한 버전에서는 각 물건의 개수가 정해져 있고, 무제한 버전에서는 몇 개든 고를 수 있습니다. 표는 이들 사이에서 조금만 달라집니다.
배낭 문제에서 탐욕 알고리즘이 맞는 경우가 있나요?
물건을 나눌 수 있는 분할 가능 배낭 문제에서는 무게당 가치가 가장 높은 것부터 고르는 것이 최적입니다. 통째로 넣는 물건에서는 결과가 크게 빗나갈 수 있지만, 탐욕 알고리즘의 결과와 가장 값진 물건 하나 중 더 나은 쪽은 항상 최대 가치의 절반 이상입니다.
표에는 메모리가 얼마나 필요한가요?
전체 표에는 (n + 1)·(W + 1)개의 칸이 필요하며, 물건을 거꾸로 읽어 내려면 이것이 필요합니다. 최대 가치만 필요하다면 W + 1칸짜리 한 행을 오른쪽에서 왼쪽으로 채우는 것으로 충분합니다.
배낭 문제는 부분집합 합 문제와 같은가요?
부분집합 합 문제는 각 물건의 가치가 무게와 같고, 배낭을 정확히 채울 수 있는지를 묻는 특수한 경우입니다. 이것도 NP-완전이며 같은 종류의 표로 풉니다.
시도해 볼 준비가 되셨나요?
브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.
배낭 문제 해 보기