Knapsack

배낭 문제는 최대한의 값어치를 낼 수 있게 제한 된 무게만큼의 물건을 가방에 넣는 문제이다.

예를 들어 limit = 10 이고 물건의 갯수가 3일 때,

weight	value
10	30
7	25
3	10

어떻게 문제를 해결할 수 있을까?

방법

1. Greedy (Fraction knapsack)
   가장 값어치가 비싼 물건을 담는다. 중량이 10인 물건을 담으면 가치는 30을 나타낸다. 하지만 이 방법은 최적의 해를 보장하지 않는다. 예를 들어 중량이 3, 7인 물건을 선택하면 가치가 35로 가치가 더 큰 해를 구할 수 있기 때문이다.

2. Dynamic Programming (0-1 Knapsack)
   가방의 제한된 무게 10까지 담는다고 고려한다면 2차원 배열로 dp[물건 수][중량] = 가치로 표현할 수 있다.
   다만 2가지 케이스로 나누어 문제에 접근해야한다.

   case 1) 현재 선택한 물건의 중량보다 가방의 제한 중량이 클 때
   case 2) 현재 선택한 물건의 중량보다 가방의 제한 중량이 작을 때

3. 물건의 갯수만큼 반복하면서 물건을 선택

4. 선택한 물건에서 limit 제한된 중량을 순회하면서 두 가지 케이스를 고려하여 가방에 담을 수 있는 물건의 가치의 최적값을 찾아야 한다.

if 가방의 중량 >= 선택한 물건의 중량
	dp[i][j] = max(dp[i-1][j], dp[i-1][j-선택한 물건의 중량] + 선택한 물건의 가치;
else
	dp[i][j] = dp[i-1][j]; //값이 작다면 이전에 선택했던 최적값을 현재 값에 저장

아래 문제를 다음과 같은 방식으로 해결할 수 있다.

백준 :평범한 배낭