Vending Machine Change
Medium · dynamic programming
A vending machine holds several kinds of coin. The coin of kind i is worth values[i], and the machine has exactly stock[i] of them, no more.
The machine has to pay out exactly amount using the coins it holds. Return the fewest coins that do it. If no selection of the coins in stock adds up to amount, return -1. An amount of 0 needs no coins, so the answer there is 0.
Examples
Example 1
Input: values = [1, 5, 10], stock = [5, 2, 1], amount = 18
Output: 5
10 + 5 + 1 + 1 + 1 = 18 uses five coins, and no four coins from the stock can make 18.
Example 2
Input: values = [2, 5], stock = [3, 1], amount = 9
Output: 3
5 + 2 + 2 = 9. The 2s alone cannot make an odd amount, so the single 5 is needed.
Example 3
Input: values = [4, 3], stock = [2, 1], amount = 10
Output: -1
Possible sums are 0, 3, 4, 7, 8 and 11. With only two 4s and one 3 there is no way to reach 10.
Constraints
- 1 <= len(values) <= 6, and len(stock) = len(values)
- 1 <= values[i] <= 500, and all values are distinct.
- 0 <= stock[i] <= 500
- 0 <= amount <= 600