배낭문제(Knapsack Problem)란,
배낭에 담을 수 있는 무게의 최댓값이 정해져 있고,
일정 가치와 무게가 있는 짐들을 배낭에 넣을 때,
가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제를 말합니다
배낭에 짐을 넣을 때,
짐을 쪼개서 넣을 수 있는 경우와 쪼개지 못하고 넣는 경우 두가지가 존재하는데,
쪼갤 수 있는 경우 분할가능 배낭문제(Fractional Knapsack Problem),
쪼갤 수 없는 경우 0-1 배낭문제(0-1 Knapsack Problem)이라 부릅니다.
쪼갤 수 없는 0-1 Knapsack의 경우 동적계획법(Dynamic Programming)으로 풀 수 있습니다.
냅색 문제는 아래 링크에서 풀어 볼 수 있습니다.
위 문제는 도둑이 가방에 넣을 수 있는 보석의 무게가 정해져 있고,
각 보석마다 무게와 가치가 입력으로 들어옵니다.
이 때 도둑이 정해진 무게만큼 보석을 넣을 때 최대 이윤을 출력하는게 문제입니다.
풀이 :
먼저, 구해야 되는 게 무엇인지 생각합니다.
-> 문제는 정해진 무게만큼 가방에 보석을 넣을 때 최대 이윤을 구하는 것입니다.
이후, 작은 문제들을 생각하고 점점 확장해서 생각해봅니다.
보석별 크기와 가치가 아래와 같다고 할 때,
보석종류 |
크기 |
가치 |
루비 |
3 |
6 |
다이아몬드 |
4 |
3 |
사파이어 |
5 |
5 |
먼저 루비 하나만 있는 경우의 가방 크기별로 루비를 넣을 때 최대이윤이 얼만지 생각합니다.
가방 크기 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 | 9 | 10 | 11 | 12 |
루비 |
0 |
0 |
0 |
6 |
6 |
6 |
6 |
6 |
6 | 6 | 6 | 6 | 6 |
다음으로 다이아몬드랑 같이 선택할 경우, 최대이윤입니다.
가방 크기 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
루비 | 0 | 0 | 0 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 |
다이아 | 0 | 0 | 0 | 6 | 6 | 6 | 6 | 9 | 9 | 9 | 9 | 9 | 9 |
- 가방의 크기가 4인 경우,
-> 다이아 챙길 경우 남은공간 0, 루비를 챙길 수 없어 가치는 3
-> 다이아를 챙기지 않을 경우, 루비를 챙길 경우의 가치를 이용해 가치는 6입니다.
-> 이 두가지 경우 중 최대 이윤 6을 저장
- 가방의 크기가 6인 경우,
-> 다이아를 챙길 경우 남은 공간 2 마찬가지로 더 보석을 못챙겨 가치는 2입니다.
-> 다이아를 챙기지 않을 경우, 구해둔 가치를 이용해 6, 최대 이윤은 6
- 가방의 크기가 7인 경우,
-> 다이아를 챙기면 남은 공간 3, 가방의 크기가 3일 떄 루비를 챙길 떄 최대이윤은 이미 6으로 구해두었습니다. 즉, 3+6 = 9 이윤은 9가됩니다.
-> 다이아를 챙기지 않은 경우 6과 9 중 최대 이윤 9가 저장됩니다.
마지막으로 사파이어를 선택할 경우, 위와같은 방법으로 비교하게 됩니다.
가방 크기 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
루비 | 0 | 0 | 0 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 |
다이아 | 0 | 0 | 0 | 6 | 6 | 6 | 6 | 9 | 9 | 9 | 9 | 9 | 9 |
사파이어 | 0 | 0 | 0 | 6 | 6 | 6 | 6 | 9 | 9 | 11 | 11 | 11 | 11 |
- 가방의 크기가 7인 경우,
->사파이어를 챙길 경우, 남은 공간 2, 남은 공간이 2일 경우 루비, 다이아 두가지 보석 모두를 이용해도 더 넣을 수가 없으므로 가치는 5,
-> 사파이어를 챙기지 않은 경우 이전에 구해둔 9가 최대이기 때문에 최대이윤은 9가됩니다.
- 가방의 크기가 8인 경우
-> 사파이어를 챙기면, 남은공간은 3, 이미 테이블을 통해 가방의 크기가 3일 때 루비/다이아를 이용해 구할 수 있는 최대 이윤은 6임을 구했습니다.
사파이어 가치 5 + ~다이아까지 넣을 떄 최대이윤 6 = 11, 즉 최대이윤이 11이 됩니다.
식을 생각해보면,
현재 내가 구하려고 하는 셀의 값은
MAX(현재 보석의 가치+남은가방크기만큼 나머지 보석을 넣을 때 최대 가치, 이전까지 구해둔 보석의 가치) 가 됩니다.
식을 세워서 풀어보면 (profit은 보석의 가치가 저장된 배열, ans는 값을 구하는 배열)
ans[i][j] = max(profit[i] + ans[i-1][j-weight[i], ans[i-1][j]]
가 됩니다.
말로 쓰려다 보니 이해가 안될 수 도 있는데요, 테이블을 직접그려서 식을 생각해보시면 도움이 될거같아요.
결국 이전에 구한 테이블값을 이용해 최대가치를 구하는 것 입니다.
(현재 테이블 값은 현재 보석 빼고 이전 보석들을 이용해서 현재 무게까지의 최대이윤 or 현재 보석을 넣고 남은 무게 중 이전 보석들로 넣을 경우 최대가치 )
참고 사이트 : http://59.23.113.171/30stair/01knapsack_doc/01knapsack_doc.php?pname=01knapsack_doc
'Software Development > Algorithm' 카테고리의 다른 글
[DP] 기업투자 문제 풀이 (1) | 2017.01.23 |
---|---|
[DP] 스티커 문제 풀이 (0) | 2017.01.21 |
Dynamic Programming (2) | 2016.07.02 |
알고리즘_타일 채우기 문제 (2) | 2016.03.06 |
Combination, n개 중 k개를 고르는 방법의 수 (0) | 2016.03.06 |