0-1 배낭문제

• 이전에 푼 문제에서 물건을 나누지 않고 1개 단위로 담을 수 있음

1. 부분 문제 정의

• 문제의 요소: 물건, 물건의 무게, 물건의 가치, 배낭의 용량
• 물건과 물건의 무게를 사용
  K[i, w] = 물건 1~i까지만 고려하고, 임시 배낭 용량이 w일 때의 최대가치
• 문제의 최적 해: K=[n, C]

2. 알고리즘

/////////초기화///////////
for i=0 to n
  K[i,0] = 0 //배낭의 용량이 0일 때 
for w=0 to C
  K[0,w] = 0 //어떠한 물건도 고려하지 않음

for i=1 to n
  for w=1 to C
    if(w_i>w)
      K[i,w] = K[i-1,w]
    else
      K[i,w] = max{K[i-1,w],K[i-1,w-w_i]+v_i}
return K[n, C]

3. 시간 복잡도

• 배열 크기를 생각하면 됨
  O(nC)
  • n: 물건 개수
  • C: 배낭의 용량