The Bag With Limited Stock
Each item type has a weight, a value, and a COUNT saying how many of it are
available. The bag holds at most C total weight. Print the largest total value.
items (w=2 v=3 x2) (w=3 v=4 x1) (w=4 v=5 x3), C = 9 -> 12
This sits between two problems already in the bank. Problem #236 is every count equal to 1, and problem #481 is every count unlimited. The two are solved by the same three lines with the inner loop running in opposite directions, and neither direction expresses a finite count greater than one.
## The two approaches that do not work
Expanding each item type into count separate copies and running 0/1 knapsack is
correct. With counts up to 1000 and 100 types that is 100000 items, and the table pass
becomes 100000 * C, which is too slow.
Looping over how many to take,
for each type:
for t from C down to 0:
for q in 0..count: dp[t] = max(dp[t], dp[t - q*w] + q*v)
is also correct and costs O(n * C * count), which is worse.
## Binary splitting
Replace a type with count x by a small set of 0/1 items whose weights are 1, 2, 4,
8, ... copies of the original, with the remainder as a final piece:
x = 11 -> pieces of size 1, 2, 4, 4
x = 7 -> pieces of size 1, 2, 4
x = 5 -> pieces of size 1, 2, 2
Take a subset of the pieces and the total number of originals is some value between 0
and x, and EVERY value in that range is reachable: the powers of two below the
remainder cover 0..2^m - 1 by binary representation, and adding the remainder piece
extends the range to x.
So the type is replaced by O(log x) 0/1 items with no loss and no gain. Run ordinary
0/1 knapsack on the flattened list.
That takes the cost from O(n * C * count) to O(n * C * log count), which at the
bounds here is the difference between running and not.
## The loop direction still matters
The flattened items are 0/1 items, so the inner loop runs DOWNWARD. Each piece may be used at most once, and using a piece twice would exceed the stock.
Getting binary splitting right and then running the loop upward silently restores
unlimited supply, and the answer comes out too high. (w=5 v=10 x1) with C = 5
answers 10; with an upward loop and C = 10 it would answer 20 for one unit of stock.
## Boundaries
(w=5 v=10 x1) with C = 4 answers 0: nothing fits, and 0 is the answer, not -1.
The bag need not be filled.
(w=3 v=7 x4) with C = 10 answers 21, three units rather than four, because the
fourth does not fit. The stock being larger than what fits must not confuse the split.