Dynamic ProgrammingBFSUnbounded Knapsack
You have coins of several denominations, each available in unlimited supply. Find the fewest coins needed to make up a given amount, or -1 if the amount cannot be made.
Input
Line 1: n (number of denominations) and the amount. Line 2: the n coin values.
Output
Print the minimum number of coins, or -1.
Constraints
1 <= n <= 12 1 <= coin <= 10^4 0 <= amount <= 5000
Example 1
Input
3 11 1 2 5
Output
3
11 = 5 + 5 + 1, which is 3 coins.
Example 2
Input
1 3 2
Output
-1
2 can never add up to 3.