484. 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.

Constraints - `1 ≤ n ≤ 100` - `0 ≤ C ≤ 10000` - `1 ≤ weight ≤ 1000` - `1 ≤ value ≤ 1000000` - `1 ≤ count ≤ 1000`