Knapsack Problem

- DP 와 Knapsack Problem : 배낭 문제는, 어떤 한 사람이 갖고 있는 배낭이 있고, 그 배낭에 담을 수 있는 최대 용량이 주어지며, 이 최대 용량에 한해서, 여러개의 물건들을 집어넣고자 할때, 최대한의 가치를 뽑아내는 방법을 찾는 문제이다. 각 물건들은 무게와 값어치가 명시되어 있고 이들 중에서 배낭에 넣을 수 있으면서, 최대의 값어치를 뽑아내는 경우의 수를 찾아내면 되는 문제이다. 배낭 문제는 다시 말하면 '여러 물건이 있을때, 특정한 조건을 만족하는 조합을 구하는 문제' 라고 볼 수 있다. 배낭 문제는 두가지 유형으로 나뉜다. 물건(짐) 을 쪼갤 수 있는 경우와 물건을 쪼갤 수 없는 경우의 두 유형으로 나뉘는데, 전자의 경우 '분할가능 배낭문제' (Fractional Knapsack..