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 <atul.87fri...@gmail.com>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.
>
--
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.
