[PS] [DP] knapsack

배낭문제라 불리는 knapsack 문제이다.

가방에 담을수 있는 무게가 정해져 있고,

가방에 물건들을 담을때 , 가치가 최대가 되는 방법을 고르는 문제이다.

dynamic programming에서 optimal solution은 항상 문제를 소분화에서 시작한다.

배낭문제의 경우 중요한점은 물건을 넣느냐, 넣지 않느냐로 나뉘게된다.

이것을 동적계획법으로 풀게되면,

위 그림과 같다.

A번 물건을 넣었을때와 넣지 않았을때를 다음 배열에 저장한후,

B번 물건을 넣었을때와 넣지 않았을때를 각각 결과에 따라 계산한다.

C번 물건도 마찬가지로 진행하되, 우리의 목적은 최대 가치를 구하는 문제이기 때문에

중첩되는 공간에는 큰 숫자가 들어가도록 한다.