정답
㉠ 조건: \(w[i] > j\), \(K[3][5]=9\), 최대 가치를 만드는 물건 번호: 2, 6, 7
출제 의도
0-1 배낭채우기에서 동적 계획법 테이블 K의 의미를 이해하고, 점화식의 분기 조건을 정확히 채우며, 주어진 w, v로 특정 칸의 값을 계산하고 최적해를 역추적해 선택 물건을 구하는 능력을 평가한다.
풀이 과정
(가)의 점화식은 용량 j에 대해 i번째 물건을 담을 수 없으면 이전 행 값을 그대로 쓰고, 담을 수 있으면 “담지 않음”과 “담음” 중 큰 값을 택하는 형태이다. 따라서 if 조건(㉠)은 i번째 물건의 용량이 j보다 큰 경우이다.
$$ \text{㉠: } w[i] > j $$
\(K[3][5]\)는 “1~3번 물건만 고려, 배낭 용량 5일 때의 최대 가치”이다. 3번 물건의 용량과 가치는 \(w[3]=5,\ v[3]=9\)이므로 담을 수 있어 다음을 계산한다.
$$ K[3][5]=\max\big(K[2][5],\ K[2][5-w[3]]+v[3]\big) =\max\big(K[2][5],\ K[2][0]+9\big) =\max(2,9)=9 $$
총용량 8에서 최댓값은 표의 \(K[7][8]=19\)이다. 이를 역추적하면 \(K[7][8]\neq K[6][8]\)이므로 7번 물건을 선택하고(남은 용량 5), \(K[6][5]\neq K[5][5]\)이므로 6번 물건을 선택한다(남은 용량 1). 이후 \(K[2][1]\neq K[1][1]\)이 되어 2번 물건을 선택하면 용량이 0이 된다.
$$ \text{선택 물건: } \{2,6,7\},\quad \text{총 용량 }=1+4+3=8,\quad \text{총 가치 }=2+8+9=19 $$
<풀이가 부정확할 수 있으니 반드시 교차검증 확인 바랍니다.>