Dynamic Programming21 sections · 916 units
Open in Course

Bounded Knapsack - Walkthrough

Limited quantities

Trace Bounded Knapsack with items [(w=2,v=3,c=2),(w=3,v=4,c=1)][(w=2, v=3, c=2), (w=3, v=4, c=1)] and capacity W=7W=7. Item 1 has 22 copies. Using binary representation: split into pseudo-items of count 11 and 11 (since 2=1+12 = 1 + 1).

Now run 0/1 Knapsack on pseudo-items: (w=2,v=3)(w=2, v=3), (w=2,v=3)(w=2, v=3), (w=3,v=4)(w=3, v=4). Result: take both copies of item 1 (w=4w=4, v=6v=6) plus item 2 (w=3w=3, v=4v=4). Total: w=7w=7, v=10v=10. Track remaining copies carefully to avoid exceeding the limit. The state space grows but the logic stays similar.