자, 이번에도 역시 문제를 풀어봄으로서 동적계획법을 더 연습해 보자.

 이번에 연습해 볼 문제도 역시 너무도 유명한 동적계획법 예제인 Knap sack문제이다. 설마 모르는 분이 있을까봐 문제설명을 드리자면.

 소유권 이전 전문가(이하 도둑)가 직업인 동섭이는 어느 날 밤 귀금속 가게를 털었다. 숙련된 솜씨로 문을 따고 가게 안에 들어가 보니 오색찬란 금덩어리 은덩어리 보석덩어리 똥덩어리(엥~ 이건 아닌가) 등등 각종 덩어리들로 눈이 부실 지경이었다. 동섭의 마음 같아서는 몽땅 털어가고 싶지만 자신이 가져온 가방이 그렇게 큰 편이 되지 못했다. 그래서 가장 값을 높게 쳐주는 보석덩어리들만 가져가려고 한다. 동섭이 가장 비싸게 처분할 수 있도록 배낭을 채워주면 된다. 단, 보석덩어리들 마다 각각의 부피와 가격은 다르다. 이 보석가게는 워낙 크기때문에 보석은 제한 없이 얼마든지 가져갈 수 있다고 한다.

 대충 이해가 되었을 것이다.

 그럼 문제를 풀기 위해 생각해 보자.

 일단 여기서는 배낭 전체을 채우는 것을 큰 문제, 배낭 일부를 채우는 것을 부분문제로 생각해 보면 문제 전체가 쉽게 풀린다.(사실 이것이 핵심이다)

 그러면 이 문제는 최적화의 원칙이 성립하게 된다. 배낭전체를 채우는 것을 큰 문제, 배낭 일부를 채우는 것을 부분문제로 생각했으므로.

 그러면 여기서는 배열을 어떻게 잡아야 할까. 위의 파란색 문장을 바탕으로 생각해보자. 감이 좀 오는가? 여기서 P라는 배열을 한번 정의해 보자.