[DP] 0/1 Knapsack(배낭) 문제

배낭문제(Knapsack Problem)란, 

배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 

일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 

가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제를 말합니다

배낭에 짐을 넣을 때,

짐을 쪼개서 넣을 수 있는 경우와 쪼개지 못하고 넣는 경우 두가지가 존재하는데,

쪼갤 수 있는 경우 분할가능 배낭문제(Fractional Knapsack Problem),

쪼갤 수 없는 경우 0-1 배낭문제(0-1 Knapsack Problem)이라 부릅니다.

쪼갤 수 없는 0-1 Knapsack의 경우 동적계획법(Dynamic Programming)으로 풀 수 있습니다.

 -> 위키백과

냅색 문제는 아래 링크에서 풀어 볼 수 있습니다.

->0/1 Knapsack 문제 보러가기

위 문제는 도둑이 가방에 넣을 수 있는 보석의 무게가 정해져 있고,

각 보석마다 무게와 가치가 입력으로 들어옵니다.

이 때 도둑이 정해진 무게만큼 보석을 넣을 때 최대 이윤을 출력하는게 문제입니다.

풀이 : 

먼저, 구해야 되는 게 무엇인지 생각합니다.

 -> 문제는 정해진 무게만큼 가방에 보석을 넣을 때 최대 이윤을 구하는 것입니다.

이후, 작은 문제들을 생각하고 점점 확장해서 생각해봅니다.

보석별 크기와 가치가 아래와 같다고 할 때,

보석종류	크기	가치
루비	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