The minimum number of coins the sum of which is S

algorithm dynamic task dynamic-programming
good_evening picture good_evening · Nov 22, 2010 · Viewed 40k times · Source

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), or report that it's not possible to select coins in such a way that they sum up to S.

I try to understand dynamic programming, haven't figured it out. I don't understand the given explanation, so maybe you can throw me a few hints how to program this task? No code, just ideas where I should start.

Thanks.

Answer

satarasu picture satarasu · May 7, 2011

The precise answer to this problem is well explained here. http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg

Related questions

What is the difference between dynamic programming and greedy approach?

What is the main difference between dynamic programming and greedy approach in terms of usage? As far as I understood, the greedy approach sometimes gives an optimal solution; in other cases, the dynamic programming approach gives an optimal solution. Are …

Read More
Split a string to a string of valid words using Dynamic Programming

I need to find a dynamic programming algorithm to solve this problem. I tried but couldn't figure it out. Here is the problem: You are given a string of n characters s[1...n], which you believe to be a corrupted …

Read More
How do I check if an array includes a value in JavaScript?

What is the most concise and efficient way to find out if a JavaScript array contains a value? This is the only way I know to do it: function contains(a, obj) { for (var i = 0; i < a.length; i++) { …

Read More