Dynamic Programming21 sections · 916 units
Open in Course

Unbounded Knapsack - Problem Statement

Infinite copies

You have nn item types. Each type ii has weight wiw_i and value viv_i. You can take each type any number of times (including zero).

Your bag holds at most WW total weight. Find the maximum value. Example: Items are (weight=2weight=2, value=3value=3) and (weight=3weight=3, value=4value=4). Capacity W=7W = 7. Take three of item 1: weight 66, value 99. But two of item 1 and one of item 2 gives weight 2+2+3=72+2+3=7, value 3+3+4=103+3+4=10. Best is 1010.