이번엔 배낭 채우기 문제에 대해 알아보겠습니다.
서론
여러분이 해외에 가는데 시중에 돈이 없어 여행사에서 제공하는 무게 이하로 짐을 싸려고 합니다.
이때 여러분은 어떻게 가방을 싸실 건가요?
술을 좋아하는 사람이라면 술을 잔뜩 챙길 것이고, 사진을 찍기 좋아하는 사람이라면 사진을 찍기 위한 물품들을 챙길 것입니다.
이렇게 한정된 공간 내에 최대의 가치로 넣는 방법을 찾는 문제가 배낭 문제입니다.
배낭 문제
배낭 문제에는 물건이 나뉠 수 있는지로 구분이 됩니다.
물건이 나뉠 수 있는 경우를 분할 가능 배낭 문제, 나뉠 수 없는 경우를 0 -1 배낭 문제라고 하죠.
각기 상황이 다르다 보니 구현하는 방법도 다른데요
먼저 물건이 나뉠 수 있는 상황 즉 분할 가능 배낭 문제에 관해 설명해드리겠습니다.
분할 가능 배낭 문제
먼저 물건을 쪼갤 수 있는 상황입니다.
아래의 물건을 7의 무게를 가진 가방에 넣는다고 할 때
| 물건 1 | 물건 2 | 물건 3 | 물건 4 | |
|---|---|---|---|---|
| 무게 | 2 | 4 | 3 | 1 |
| 가치 | 5 | 8 | 9 | 1 |
무게당 가치가 높은 순서대로 더 넣을 수 없을 때까지 꽉꽉 넣으면 됩니다.
엥 그게 끝이야?
네.
아래와 같이 무게당 가치를 구해주고
| 물건 1 | 물건 2 | 물건 3 | 물건 4 | |
|---|---|---|---|---|
| 무게당 가치 | 2.5 | 2 | 3 | 1 |
가장 높은 순서대로 (3번, 1번, 2번, 4번) 넣어주면 됩니다.
가방에 3과 1번 그리고 2번 절반을 넣는다면 최대 18의 가중치로 넣을 수 있겠네요.
0 - 1 배낭 문제
하지만 아래의 경우라면 어떨까요?
여권을 찢어도 되나요? 돈을 찢어도 되나요?
이렇게 쪼갤 수 없는 물건들을 가방에 최대의 가치로 넣는 경우를 0 -1 배낭 문제라고 합니다.
위 경우는 어떻게 풀어야 할까요? 위처럼 풀어도 될까요?
한번 해보겠습니다.
| 물건 1 | 물건 2 | 물건 3 | 물건 4 | |
|---|---|---|---|---|
| 무게 | 2 | 4 | 3 | 1 |
| 가치 | 5 | 8 | 9 | 1 |
| 무게당 가치 | 2.5 | 2 | 3 | 1 |
무게당 가치 순서대로 가방에 먼저 넣어보겠습니다.
3번 물건을 넣으니 가방에 4의 공간이 남고, 현재 가치는 9가 있네요.
1번 물건을 넣어보겠습니다.
1번 물건을 넣으니 가방에 2의 공간이 남고, 현재 가치는 14가 있습니다.
자 이제 물건 2를 넣어보겠습니다.
어라? 근데 가방엔 2의 공간밖에 없고 물건 2는 무게가 4라 못 넣네요.
그럼 정답이 3번과 1번 물건만 넣은 14가 끝일까요?
아닙니다. 물건 4를 더 넣을 수 있기도 하고, 실재 답도 아닙니다.
따라서 물건을 쪼갤 수 없는 경우는 위처럼 풀 수 없고 다이나믹 프로그래밍으로 풀어야 합니다.
| 물건 1 | 물건 2 | 물건 3 | 물건 4 | |
|---|---|---|---|---|
| 무게 | 2 | 4 | 3 | 1 |
| 가치 | 5 | 8 | 9 | 1 |
다시 위의 물건들을 7의 무게를 가진 가방에 넣어보겠습니다.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
|---|---|---|---|---|---|---|---|---|
| 물건 1 | - | - | - | - | - | - | - | - |
| 물건 2 | - | - | - | - | - | - | - | - |
| 물건 3 | - | - | - | - | - | - | - | - |
| 물건 4 | - | - | - | - | - | - | - | - |
먼저 1번 물건을 넣어보겠습니다.
물건 1번은 2의 무게와 5의 가치를 가지고 있네요.
1번 물건을 넣어주겠습니다.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
|---|---|---|---|---|---|---|---|---|
| 물건 1 | 0 | 0 | 5 | 5 | 5 | 5 | 5 | 5 |
| 물건 2 | - | - | - | - | - | - | - | - |
| 물건 3 | - | - | - | - | - | - | - | - |
| 물건 4 | - | - | - | - | - | - | - | - |
자 이제 2번 물건을 넣어보겠습니다.
2번 물건은 4의 무게와 8의 가치를 가지고 있네요.
가방의 무게가 4인 경우 물건 1번보다는 가치가 더 높은 2번을 넣는 게 좋겠죠?
그리고 가방의 무게가 6인 경우엔 1번과 2번 둘 다 들어갈 수 있겠네요.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
|---|---|---|---|---|---|---|---|---|
| 물건 1 | 0 | 0 | 5 | 5 | 5 | 5 | 5 | 5 |
| 물건 2 | 0 | 0 | 5 | 5 | 8 | 8 | 13 | 13 |
| 물건 3 | - | - | - | - | - | - | - | - |
| 물건 4 | - | - | - | - | - | - | - | - |
자 이제 물건 3번을 넣어보겠습니다.
물건 3번은 3의 무게와 9의 가치를 가지고 있네요.
가방의 무게가 3인 경우에 1번 물건 대신 3번 물건을 넣는 게 좋겠네요.
그뿐만 아니라 가방의 무게가 5인 경우엔 1번 물건과 3번 물건이 같이, 무게가 7인 경우엔 2번 물건과 3번 물건이 들어가면 가치가 최대로 되겠네요.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
|---|---|---|---|---|---|---|---|---|
| 물건 1 | 0 | 0 | 5 | 5 | 5 | 5 | 5 | 5 |
| 물건 2 | 0 | 0 | 5 | 5 | 8 | 8 | 13 | 13 |
| 물건 3 | 0 | 0 | 5 | 9 | 9 | 14 | 14 | 17 |
| 물건 4 | - | - | - | - | - | - | - | - |
마지막으로 4번 물건을 넣어보겠습니다.
가방의 무게가 1인 경우엔 4를 넣고, 무게가 4인 경우엔 3번과 같이, 무게가 6인 경우엔 3번과 1번과 같이 넣으면 되겠네요.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
|---|---|---|---|---|---|---|---|---|
| 물건 1 | 0 | 0 | 5 | 5 | 5 | 5 | 5 | 5 |
| 물건 2 | 0 | 0 | 5 | 5 | 8 | 8 | 13 | 13 |
| 물건 3 | 0 | 0 | 5 | 9 | 9 | 14 | 14 | 17 |
| 물건 4 | 0 | 1 | 5 | 9 | 10 | 14 | 15 | 17 |
자 이렇게 모든 물건을 탐색해보았습니다.
물건을 쪼갤 수 없는 경우엔 분할 가능한 상황과 달리 최대 17의 가중치로 넣을 수 있네요.
결론
분할 가능한 배낭 문제는 Greedy Algorithm으로, 0 - 1 배낭 문제는 Dynamic Programming으로 푼다.
마무리하며
최대한 열심히 작성하였으나 사람이다 보니 부족한 점이 있을 수 있습니다.
틀린 부분이나 부족한 부분을 발견하신다면 말씀해주세요.
바로 고치도록 하겠습니다.
감사합니다.
