DP | 작은 부분 문제 해결

1. 완전 탐색을 생각한다.
2. 작은 부분 문제부터 해결해나간다.
3. 상향식으로 코드를 구현한다.

완전탐색

모든 아이템에 대해 모든 kg에 대해 완전탐색을 한다. 가방이 10kg 이라면, 1kg부터 10kg까지 모든 최적해를 구해나간다. 우리가 원하는 건 마지막 아이템까지 검사한 마지막 10kg에 대한 최적해를 구하는 것이다.

작은 부분 문제 해결

dp[i][w] = Math.max(dp[i-1][w], dp[i-1][ w - weights[i] ] + profits[i]);

i-1 이란 것은 i번째 물건을 채우기 전 상태를 뜻하는데,
(i번째 물건을 채우기 전 상태에서) i번째 물건을 담지 않을 경우와
(i번째 물건을 채우기 전 상태에서) i번째 물건을 담을 경우(이 경우 해당 i번째 물건의 가치 더해주기)
두 가지 경우의 최적해에서 최대값이 해당 i에서 최적해가 되는 것이다.

---

📌 예제. 배낭문제(Knapsack)

---

상향식으로 구현