The classical coin-changing problem can be stated as follow:
Given an integer set C={c_1, c_2, ... c_n} where c_1=1 and c_i c_{i
+1}, and an positive integer M,
find the minimum of \sum_{i=1}^n x_i, where all x_i's are non-negative
integers and subject to \sum_{i=1}^n x_i c_i = M
And it is well
the greedy algorithm yields an optimal solution for the coin problem when
c1, c2,c3, ..., ck in decreasing order where ci is value of the coin
a1*c1 = a2*c2 = a3*c3 = a4*c4 = ... = ak*ck
a1 a2 a3 ... ak
1*50= 5*10 = 10*5 = 50*1
satisfy this condition.
I think this condition is necessary
Hi all,
Pls help me with the solution to the following problem related to the coin
changing problem.
suppose that the available coins a ein the denominations c^0, c^1 , c^2...
c^k for some intgers c1 and k=1. show tht the greedy algorithm always
yeilds an optimal solution
thanks in advance
int denom(int Coin[],int n,int amount)
{
for(i=0;in;++i)
{
c=Coin[i];
for(j=c;j=amount;++j)
{
den[j]+=d[j-c];
}
}
return den[amount];
}
On Wed, Oct 6, 2010 at 4:43 AM, pre lak pre.la...@gmail.com wrote:
Hi all,
Pls help me with the solution to the following problem related to the coin
show tht the greedy algorithm always yeilds an optimal solution??/
On Tue, Oct 5, 2010 at 7:47 PM, sharad kumar aryansmit3...@gmail.comwrote:
int denom(int Coin[],int n,int amount)
{
for(i=0;in;++i)
{
c=Coin[i];
for(j=c;j=amount;++j)
{
den[j]+=d[j-c];
}
}
return den[amount];
}
hello guys,
Can anybody solve the following coin changing and knapsack problem?
[coin change] Let {c1, c2, …., cn=1} be a set of distinct coin types,
where each ci is an integer. Each type is available in unlimited
quality. The coin changing problem is to make up an exact amount M
using a minimum
