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 [email protected].
