Unlimited to Limited

You've seen 0/1 knapsack (each item once) and unbounded knapsack (unlimited copies). Bounded knapsack sits in between: each item has a limit $k_i$ on how many copies you can take. The naive approach: treat item $i$ as $k_i$ separate items and run 0/1 knapsack.

But if $k_i = 1000$ for many items, this explodes. There's a clever trick using binary representation that reduces $k$ copies to $\log(k)$ items. I'll show you how.