You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
279. Given a list of N coins, their values (V1, V2, … , VN), and the total sum S. Find the minimum number of coins the sum of which is S (we can use as many coins of one type as we want), if it is not possible to select coins in such a way that they sum up to S then print '-1'. Example: Given coins with values 1, 3, and 5. And the sum S is 11. Output: 3, 2 coins of 3 and 1 coin of 5
279. Given a list of N coins, their values (V1, V2, … , VN), and the total sum S. Find the minimum number of coins the sum of which is S (we can use as many coins of one type as we want), if it is not possible to select coins in such a way that they sum up to S then print '-1'. Example: Given coins with values 1, 3, and 5. And the sum S is 11. Output: 3, 2 coins of 3 and 1 coin of 5
Given a list of N coins, their values (V1, V2, … , VN), and the total sum S. Find the minimum number of coins the sum of which is S (we can use as many coins of one type as we want), if it is not possible to select coins in such a way that they sum up to S then print '-1'.
Example: Given coins with values 1, 3, and 5. And the sum S is 11.
Output: 3, 2 coins of 3 and 1 coin of 5
Input Size : N<=10000
Example:
INPUT
3 11
1 3 5
OUTPUT
3
n, s = map(int, input().split())
coins = list(map(int, input().split()))
dp = [[float("inf") for i in range(s + 1)] for j in range(n + 1)]