Knapsack problem

무게의 최대값이 정해져 있을때, 가치의 합이 최대가 되도록 짐을 고르는 문제

Fraction

• 물건을 쪼갤 수 있는 문제
  가치가 큰 물건 부터 담고, 남은 무게 만큼 무게를 쪼갠다. -> greedy

0/1

• 물건을 쪼갤 수 없는 문제
  동적 계획법으로 해결.
  dp[i][j] = i번째 물건까지 넣을 수 잇고, 배낭에 넣은 물건 무게의 합이 j일때 최대 이윤을 저장함.

각 가방의 가치 : v[n]

각 가방의 무게 : w[n]

최대이윤 : dp[m][n]이라 할 때,
(w[i] <= j ) dp[i][j] = max(v[i] + dp[i-1]j - w[i]], dp[i-1][j]
(w[i] > j) dp[i][j] = dp[i-1][j]

• 집합 A가 n번째 보석을 포함하고 있지 않다면, A는 n번째 보석을 뺀 나머지 n-1개의 보석들 중에서 최적으로 고른 부분집합과 같다.

• 집합 A가 n번째 보석을 포함하고 있다면, A에 속한 보석들의 총 가격은 n-1개의 보석들 중에서 최적으로 고른 가격의 합에다가 보석 n의 가격을 더한 것과 같다. (단, n번째 보석을 넣었을 때 배낭이 터지지 않아야 한다)

출처: https://gsmesie692.tistory.com/113 [환상빛 별하늘: Reb∞t]

https://gsmesie692.tistory.com/113