Efficient algorithm?
in [Theory]
|
Prev: CS conference ranking reference at www.conference-ranking.net
Next: Free software JFLAP alternative?
From: Ez_Alg on 18 Mar 2007 22:12 Given an unlimited supply of coins of denominations x1; x2; : : : ; xn, we wish to make change for a value v using at most k coins; that is, we wish to find a set of k coins whose total value is v. This might not be possible: for instance, if the denominations are 5 and 10 and k = 6, then we can make change for 55 but not for 65. what is an efficient dynamic-programming algorithm for the following problem. Input: x1; : : : ; xn; k; v. Question: Is it possible to make change for v using at most k coins, of denominations x1; : : : ; xn? any help would be appriciated.
From: Googmeister on 19 Mar 2007 09:07 On Mar 18, 10:12 pm, "Ez_Alg" <virtualreal...(a)gmail.com> wrote: > Given an unlimited supply of coins of denominations x1; x2; : : : ; > xn, we wish to make change for a value v using at most k coins; that > is, we wish to find a set of k coins whose total value is v. > This might not be possible: for instance, if the denominations are 5 > and 10 and k = 6, then we can make change for 55 but not for 65. what > is an efficient dynamic-programming algorithm for the following > problem. > Input: x1; : : : ; xn; k; v. > Question: Is it possible to make change for v using at most k coins, > of denominations x1; : : : ; xn? > any help would be appriciated. By "efficient", does your instructor mean poly-time as a function of n, k, and v or as a function of the input size (n, log k and log v)? The coin-changing problem is NP-complete.
From: Mitch on 19 Mar 2007 16:02
On Mar 18, 9:12 pm, "Ez_Alg" <virtualreal...(a)gmail.com> wrote: > Given an unlimited supply of coins of denominations x1; x2; : : : ; > xn, we wish to make change for a value v using at most k coins; that > is, we wish to find a set of k coins whose total value is v. > This might not be possible: for instance, if the denominations are 5 > and 10 and k = 6, then we can make change for 55 but not for 65. what > is an efficient dynamic-programming algorithm for the following > problem. > Input: x1; : : : ; xn; k; v. > Question: Is it possible to make change for v using at most k coins, > of denominations x1; : : : ; xn? > any help would be appriciated. Dynamic programming means remember results on (structured) subsets of the input. Often (as is probably best in this case) you'll remember it in a table. What do you think your table should look like? Now... how do you fill out that table? Consider denomination 'xn'. There's a solution for v using a single coin of size xn if...what? (that's gives you your recursive function to help compute the table). Mitch |