🚩무제한 배낭 문제

Q1.동일한 물건을 여러번 담을 수 있는 때, 최대가치?

동일한 물건을 여러 번 선택할 수 있을 때 0-1 Knapsack과 점화식이 달라진다.

🤔 0/1 배낭문제와 무제한 배낭 문제의 차이

0/1 배낭 문제는 물건을 한 번만 선택할 수 있기 때문에, 선택하는 순간 해당 물건의 가치는 더 이상 고려되지 않는다.
따라서, 이전 물건까지의 가치만을 고려해야 한다.
(dp[i][w], dp[i-1][w]를 사용한 이유)

무제한 배낭 문제에서는 동일한 물건을 여러 번 선택할 수 있으므로, 이전 물건까지의 가치에 구애받지 않고, 현재 물건을 여러 번 포함할 가능성을 계속 고려해야 한다.

즉 점화식은 dp[w] = max(dp[w], dp[w - weights[i]] + values[i]) 이다.