정의

배낭 문제 중에는 물건의 무게를 쪼갤 수 있는 fraction knapsack 문제와 쪼갤 수 없는 0-1 knapsack 문제로 구분할 수 있다.

문제

평범한 배낭 문제(백준)

풀이

  • 가로열에는 배낭의 크기를 입력하여 각 열은 가방이 j만큼의 무게를 감당할 수 있는 경우의 수이다.
  • dp[i][j]에서 i는 i번째 물건까지 고려하면서 최대로 담을 수 있는 배낭의 무게가 j일때의 최대 가치를 갖는다. ( i번 째 물건을 넣지 않은 경우와 넣은 경우 중 더 큰 가치를 반영하도록 한다.)
  • 점화식은 아래와 같을 것이다.
if (j < w[i]) {
				dp[i][j] = dp[i-1][j];
			}
			else {
				dp[i][j] = max(dp[i - 1][j], v[i] + dp[i - 1][j - w[i]]);
			}

참조