How about this:
const int N = 6;
unsigned int coins[N] = {100,50,25,10,5,1};
unsigned int count[N] = {2, 1, 1, 5, 4, 10};
int best = 1000000000;
int minCoins(int s, int f=0, int d=0)
{
if (d == 0) best = s; // It can never take more than s coins
if (s < 1) return 0; // No coins required
if (d >= best) return 100; // We've already used too many coins.
int result=best;
for(int i = f; i < N; ++i) // Don't regress
{
if (count[i]) // Only try coins which are available
{
if (coins[i] < s) // Try using this coin
{
--count[i];
int sum = 1 + minCoins(s-coins[i], i, d+1);
if (sum < result) sum = result;
if ((d == 0) && (sum < best)) best = sum;
++count[i];
}
else if (coins[i] == s) return 1; // This coin is all we need
}
}
return result;
}
int main()
{
int s;
scanf("%d", &s);
printf("The fewest coins to total to %d is %d\n", s, minCoins(s));
return 0;
}
On Thursday, May 15, 2014 1:35:12 AM UTC-4, atul007 wrote:
>
> Solving coin change problem with limited coins.
>
> Given an array of denominations and array Count , find minimum number of
> coins required to form sum S.
>
> for eg: coins[]={1,2,3};
> count[]={1,1,3};
> i.e we have 1 coin of 1$ , 1 coin of 2$ , 3 coins of 3$.
>
> input S = 6
> output = 2
>
> possible combination : 3+3 = 6
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
