@atul007..
I think the solution that you have given is to solve the coin denomination
problem... where the denominations range from 1 to R..
But that's not the question..
The question is :
Given R and N, we need to find a set of coins where the set size is N (out
of all R(C)N combinations available) such that for the given set the
average no. of coins required to represent any denomination from 1 to R is
minimal.
And also the coin denominations available range from 1 to R (themselves)..
Hence the problem is to print those set of N coins out of R coins such that
the average is minimized.
If I understood @Dave correctly then the question that he has asked is
whether given the above problem statement :
1) we can use multiple denominations of the same kind (i.e. whether we have
infinite supply of any denomination)
2) or we can use a denomination of a particular value only once ?
@shady..
What do you mean by "average no. of coins" ? Which one of the following
are you looking for ?
a) Say Xi denotes the no. of coins required to represent value i, where 1
<=i <=R..
Minimum average would be = min { { for a particular pick of N coins - >
(X1 +X2 + .... + XR)/R } }
b) Say Xi denotes the no. of coins required to represent value i, where 1
<=i <=R..
Minimal value = min { { for a particular pick of N coins - > max { Xi } } }
On Saturday, 22 December 2012 03:31:52 UTC+5:30, shady wrote:
>
> Given R and N, output N coins in the range from 1 to R such that average
> number of coins needed to represent all the number in the range is
> minimized.
>
> Any idea ? hints ?
>
--
