Bounded Knapsack - Binary Representation

Instead of treating 7 copies as 7 separate items, represent 7 in binary: $7 = 1 + 2 + 4$. Create three "bundle" items with weights $w, 2w, 4w$ and values $v, 2v, 4v$. Any quantity from 0 to 7 can be formed by including/excluding these bundles. Want 5 copies? Take the bundles for 1 and 4. Want 3? Take 1 and 2. This reduces $k$ items to $\lceil \log_2(k+1) \rceil$ items. Now run standard 0/1 knapsack. Total time: $O(n \times W \times \log k)$.

Time complexity: $O(n \times W \times \log k)$.

Space complexity: $O(W)$ for the dp array.