Bounded Knapsack - Why Naive Is Slow

The naive transition tries all quantities from 0 to $k_i$:

for each item (w, v, k)
 for capacity from W down to 0
 for count from 0 to k
 if capacity ≥ count * w then
 dp[capacity] = max(dp[capacity], dp[capacity - count*w] + count*v)

If you have $100$ items, each with quantity 1000, and capacity 10000, that's $10^{11}$ operations. Way too slow. The trick is to convert bounded knapsack into 0/1 knapsack with fewer items. Binary representation makes this possible.