The bounded knapsack pattern

Coins with a limited supply, ingredients with limited stock, machines that can be used a few times: these are knapsacks where item i has count[i] copies. The two standard treatments carry over to any operator:

• Try every count: for each item, the new value at total t is the best over k = 0..count of old[t − k · w] combined with k copies. Fine for small counts.
• Binary splitting: rewrite count as bundles 1, 2, 4, …, remainder and run the 0/1 pattern over the bundles. Correct for min and max. For counting it overcounts (different bundle choices can give the same number of copies), so counting uses the first method or a prefix-sum version of it.

Binary splitting is safe whenever the operator is idempotent (min, max, or): reaching the same count of copies two ways does no harm. For sums of ways, it double counts.

The problems in this module:

• The fewest coins from a limited supply
• Ways to pay with a limited supply