The main difference between the standard CC algo, and the one with limited
coin supply is the maximum value that we can form with the given coins.
For example :
In stranded CC
coins = {1,2,3}
then we can can form denominations to any value(assuming that coin with 1
value will always be there). But in case the provided coins are limited
then we can form the denominations only up to the partial sum:
Ex:
coins[] = {1,2,3}
count[] = {1,1,2}
then we can form the denominations only up to 1*1+2*1+3*2 = 9. But this
value is only valid if we take all the coins into the consideration. But if
you take only two coins {1,2} then we can form denominations only up to 3.
So the modified algorithm is
Pick the current coin
Use the coin to form denominations till it's partial sum.
Code Snippet:
public static void coinChange(int max_value, int coins[], int count[]) {
int coins_sz = coins.length;
int dp[] = new int[max_value + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
int partial_sum = 0;
for (int i = 0; i < coins_sz; i++) {
partial_sum += coins[i] * count[i];
for (int j = coins[i]; j <= partial_sum && j <= max_value; j++) {
dp[j] = Math.min(dp[j - coins[i]] + 1, dp[j]);
}
}
for (int i = 1; i <= max_value; i++) {
System.out.println("Coin value = " + i
+ ", Minimum number of coins = " + dp[i]);
}
}
Let me know in case the above algorithm fails for any test cases.
On Thu, May 15, 2014 at 11:05 AM, atul anand <[email protected]>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].
>
--
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].
