Knap Sack

1. 개요

이번에는 knap sack 문제에 대해서 알아보았다.

knap sack은 보석의 무게와 가격이 있을 때, 어떻게 최대로 높은 가격의 보석을 제한된 무게 안으로 챙길 수 있는지에 대한 문제이다.

이를 dynamic programming으로 코드를 작성해서 해결하게 된다.

0, 1, 2, 3, 4, 5 는 가방의 최대 무게가 0일 때, 1일 때, ...을 의미한다.

 

이전 보석을 확인하고, 다음 보석을 확인할 때는 2가지 경우가 생기게 된다.

1. 보석이 남은 가방의 무게를 초과할 때
2. 보석을 가방에 넣을 수 있을 때 -> 보석을 가방에 넣을 것인가, 넣지 않을 것인가.

로 나뉘게 된다.

 

이런 점화식을 기반으로 코드를 작성하게 된다.

 

점화식에서 B[i][w] = max(B[i-1][w], B[i][w - wi] + val(wi)) 부분이 이해가 잘 되지 않곤 했다.

무조건 보석을 넣으면 가치가 증가하는 거 아닌가?

아니다. B[i][w-wi] 는 w-wi 값에서의 최대 가치를 나타내는 것이기 때문에, 해당 위치에서의 가치와 val(wi)와의 합이 B[i-1][w] 보다 작을 수 있는 것이다. 

 

만약 i가 4라고 가정하고, w는 5라고 가정하고, wi의 무게가 2라고 가정했을 떄, 

B[4][5]= max(B[3][5] , B[4][3] + val(3)) 이 되는 것이고 [3][5]는 이전 5의 무게를 가방이 담을 수 있을 떄의 무게를 의미하며, 

[4][3]은 가방에 3의 무게를 담을 수 있을 때, 그리고 보석 4개를 헤아렸을 때의 최대 무게를 의미한다.

2. 코드

https://www.geeksforgeeks.org/0-1-knapsack-problem-dp-10/

0/1 Knapsack Problem - GeeksforGeeks

 

코드는 내가 사랑하는 geeks for geeks를 확인하였다. 

그 중 첫 번째(재귀)와, 세 번째(반복) 코드를 확인하였다.