You have coins with different denominations and you have limited number of each denominations (some maybe zero), how will you determine if you can supply the given change ?
Approach:
Characterize the structure of a coin-change solution.
• Define C[j] to be the minimum number of coins we need to
make change for j cents.
• If we knew that an optimal solution for the problem of
making change for j cents used a coin of denomination di,
we would have:
C[j] = 1 + C[j - di]
C[j] = infinite if j < 0
= 0 if j == 0;
= 1 + min { C[j - D[i]] } if j >= 1;
1<=i<=k
Now here we *DO NOT* have unlimited coins, so we keep one more array of limit of each type of coin denominations.
Let coin denominations be:
int [] D = {50, 25, 10, 1};
Ex for above coin denominations
int [] limit = {2, 1, 2, 5};
Now please refer "makeChangeLimitedCoins" method implementation in the below code for more..
If we want to make change for 30, with the above coin denominations and limit then below code outputs the following:
Printing Coin Value and Change:
1:1
2:2
3:3
4:4
5:5
6: Not Possible
7: Not Possible
8: Not Possible
9: Not Possible
10:1
11:2
12:3
13:4
14:5
15:6
16: Not Possible
17: Not Possible
18: Not Possible
19: Not Possible
20:2
21:3
22:4
23:5
24:6
25:1
26:2
27:3
28:4
29:5
30:6
Approach:
Characterize the structure of a coin-change solution.
• Define C[j] to be the minimum number of coins we need to
make change for j cents.
• If we knew that an optimal solution for the problem of
making change for j cents used a coin of denomination di,
we would have:
C[j] = 1 + C[j - di]
C[j] = infinite if j < 0
= 0 if j == 0;
= 1 + min { C[j - D[i]] } if j >= 1;
1<=i<=k
Now here we *DO NOT* have unlimited coins, so we keep one more array of limit of each type of coin denominations.
Let coin denominations be:
int [] D = {50, 25, 10, 1};
Ex for above coin denominations
int [] limit = {2, 1, 2, 5};
Now please refer "makeChangeLimitedCoins" method implementation in the below code for more..
If we want to make change for 30, with the above coin denominations and limit then below code outputs the following:
Printing Coin Value and Change:
1:1
2:2
3:3
4:4
5:5
6: Not Possible
7: Not Possible
8: Not Possible
9: Not Possible
10:1
11:2
12:3
13:4
14:5
15:6
16: Not Possible
17: Not Possible
18: Not Possible
19: Not Possible
20:2
21:3
22:4
23:5
24:6
25:1
26:2
27:3
28:4
29:5
30:6
This comment has been removed by the author.
ReplyDeleteHi,
ReplyDeleteDoes this implementation works for coins 6,6,6,12 and value 24?
Yes this has an error. I've corrected it. But I never ran it. Pls do minor corrections
ReplyDeletepublic static void makeChangeLimitedCoins(int [] D, int [] S, int N) {
int [] C = new int [N+1];
C[0] = 0;
int len = D.length;
int [][] track = new int[N+1][len];
for (int i=0; i= D[k] && (C[j-D[k]] < Integer.MAX_VALUE) && (track[j-D[k]][k] > 0)) {
//C[j] = C[j] > 1+C[j-D[k]] ? 1+C[j-D[k]] : C[j];
if ((C[j] > 1+C[j-D[k]])) {
C[j] = 1 + C[j-D[k]];
denom[j] = D[k];
/**********************Change****************/
for(int m=0;m<len;m++){
if(m==k){
track[j][m] = track[j-D[k]][m] - 1;
}
else{
track[j][m] = track[j-D[k]][m];
}
}
track[j][k] = track[j-D[k]][k] - 1;
} else {
//track[j][k] = track[j-D[k]][k];
}
/**********************Change****************/
} else if (j < D[k] ){
track[j][k] = track[0][k];
}
}
}
System.out.println("Printing Coin Value and Change:");
for (int i=1; i<=N; i++) {
if (C[i] == Integer.MAX_VALUE) {
System.out.println(i + ":" + " Not Possible");
} else {
System.out.println(i + ":" + C[i]);
}
}
System.out.println();
for (int i=0; i<=N ;i++) {
System.out.print(i + ": ");
for (int j=0; j<len; j++) {
System.out.print(track[i][j] + " ");
}
System.out.println();
}
//System.out.println("Printing change for: " + (N));
//printCoins(denom, N);
}
Solution will not work for below case :
ReplyDeleteint[] D = { 33, 30, 20, 66 };
int[] limit = {10 , 2, 2 , 10 };
makeChangeLimitedCoins(D, limit, 100);