Limited Stock Knapsack — Solution & Editorial

Back to the Problem

Binary-split each bounded item into groups of size 1, 2, 4, ... (and a remainder), turning it into a 0/1 knapsack — O(NW log c). A monotonic-deque grouping does O(NW).

Complexity: O(N W log c)

Watch out: Naively expanding c copies is O(N W ∑c) and times out — the log split is essential.