Need help with coin change problem - Dynamic Programming technique. It is produc
ID: 3708277 • Letter: N
Question
Need help with coin change problem - Dynamic Programming technique.
It is producing wrong output.
package assn;
public class cc {
public static int min(int a, int b) {
if (a > b) {
return b;
}
else {
return a;
}
}
public static int minCoin(int n, int m, int wt[], int memo[]) {
if (memo[n] != -1) {
return memo[n];
}
if (m == 0) {
return 0;
}
if (n == 0) {
return m;
}
if (m < wt[n]) {
return minCoin(n - 1, m, wt, memo);
}
else {
memo[n] = min(minCoin(n - 1, m, wt, memo), 1 + minCoin(n, m - wt[n], wt, memo));
return memo[n];
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
// code
long startTime = System.nanoTime();
int n = 5;
int m = 227;
int wt[] = new int[6];
wt[0] = 1;
wt[1] = 2;
wt[2] = 5;
wt[3] = 10;
wt[4] = 25;
wt[5] = 75;
int memo[] = new int[7];
for (int i = 0; i < 6; i++) {
memo[i] = -1;
}
int ans = minCoin(n, m, wt, memo);
System.out.println("" + ans);
}
}
Explanation / Answer
#include<stdio.h>
int count( int S[], int m, int n )
{
int i, j, x, y;
// We need n+1 rows as the table is constructed
// in bottom up manner using the base case 0
// value case (n = 0)
int table[n+1][m];
// Fill the enteries for 0 value case (n = 0)
for (i=0; i<m; i++)
table[0][i] = 1;
// Fill rest of the table entries in bottom
// up manner
for (i = 1; i < n+1; i++)
{
for (j = 0; j < m; j++)
{
// Count of solutions including S[j]
x = (i-S[j] >= 0)? table[i - S[j]][j]: 0;
// Count of solutions excluding S[j]
y = (j >= 1)? table[i][j-1]: 0;
// total count
table[i][j] = x + y;
}
}
return table[n][m-1];
}
// Driver program to test above function
int main()
{
int arr[] = {1, 2, 3};
int m = sizeof(arr)/sizeof(arr[0]);
int n = 4;
printf(" %d ", count(arr, m, n));
return 0;
}