Bounded Knapsack - Implementation

Here's the full solution:

function boundedKnapsack(items, W)
    // Convert bounded items to binary bundles
    bundles := empty list
    Each (w, v, k) in items
        power := 1
        while power ≤ k
            bundles.add((w * power, v * power))
            k := k - power
            power := power * 2
        if k > 0
            bundles.add((w * k, v * k))
    // Standard 0/1 knapsack on bundles
    dp := array of size (W + 1), all 0
    Each (bw, bv) in bundles
        for w from W down to bw
            dp[w] := max(dp[w], dp[w - bw] + bv)
    return dp[W]

Time: $O(W \times \sum \log k_i)$. Space: $O(W)$.

The binary decomposition is the key. Instead of $k$ copies of each item, you create $O(\log k)$ bundles. Any count from $1$ to $k$ can be formed by combining these bundles. This makes bounded knapsack nearly as fast as 0/1.