For this problem, as we try to find the number of combinations of coins that sum up to a certain amount. We search through every possible combination of coins using a recursive routine that keeps track of previously solved subproblems (combinations of coins that sum up to a different, smaller amount) in a 2 dimensional array. One dimension is used to look up the amount of money the coins sums up to, and the second dimension is used to keep track of what subset of coins are used for the sub problem.
It is important to account for the fact that the order of the coins is irrelevant, this is accomplished by restricting the recursive calls of the search to using either the last used coin (to allow for multiple coins of the same type) or a subset coins that have not already been used.
#include <stdio.h>
int v, n;
int coins[25];
long long num_ways[25][10001];
/* search for how many combinations of coins which have
an index >= lowest_coin, that sum up to amount */
long long search(int amount, int lowest_coin) {
if (amount < 0) return 0;
if (num_ways[lowest_coin][amount] != -1)
return num_ways[lowest_coin][amount];
long long total = 0;
for (int i = lowest_coin; i < v; i++) {
total += search(amount - coins[i], i);
}
num_ways[lowest_coin][amount] = total;
return total;
}
int main() {
freopen("money.in", "r", stdin);
freopen("money.out", "w", stdout);
scanf("%d%d", &v, &n);
for (int i = 0; i < v; i++)
scanf("%d", &coins[i]);
for (int j = 0; j < v; j++) { /* initialize the subproblem lookup
array */
for (int i = 1; i <= n; i++)
num_ways[j][i] = -1;
num_ways[j][0] = 1;
}
printf("%lld\n", search(n, 0));
return 0;
}
This is a DP problem that can be computed recursively the only thing you should take care of is integer overflows so you can use c++ long long or java long or BigInteger class. Given that the amount needed is V that uses K coins. You can compute the number of ways using all the first K-1 coins except the last one or you can compute it with all the K coins.
Compute(v,k)= the number of ways using all the first K-1 coins except the last one+ compute it with all the K coins
Compute(v,k)= compute(v,k-1) /*all but the last one*/ + compute(v-coins[k],k) /*using the last one then the remaining value is v-coins[k]*/
Here is wahab1 java solution using java BigInteger class
/*
ID: wahab1
PROG: money
LANG: JAVA
*/
import java.math.*;
import java.io.*;
import java.util.*;
public class money
{
static int coins[]=new int[25];
static BigInteger val[][]=new BigInteger[25][10001];
public static BigInteger compute(int v,int k)
{
if(k==0)
return v%coins[k]==0?BigInteger.ONE:BigInteger.ZERO;
if(v==0)
return BigInteger.ONE;
if(v<0)
return BigInteger.ZERO;
if(val[k][v]!=null)
return val[k][v];
return val[k][v]=compute(v,k-1).add(compute(v-coins[k],k));
}
public static void main(String[] args) throws Exception
{
FileReader in=new FileReader("money.in");
PrintWriter out=new PrintWriter(new FileWriter("money.out"));
StreamTokenizer st=new StreamTokenizer(in);
int n,v;
st.nextToken();
n=(int)st.nval;
st.nextToken();
v=(int)st.nval;
for(int i=0;i<n;i++)
{
st.nextToken();
coins[i]=(int)st.nval;
}
out.println(compute(v,n-1));
out.close();
}
}
Neal Wu writes:
The following is a simple and fast iterative solution that uses only O(N) memory:
#include <cstdio>
using namespace std;
FILE *fout = fopen ("money.out", "w");
FILE *fin = fopen ("money.in", "r");
const int MAXN = 10005;
int V, N, C;
long long nways [MAXN];
int main ()
{
nways [0] = 1;
fscanf (fin, "%d %d", &V, &N);
while (V--)
{
fscanf (fin, "%d", &C);
for (int i = 0; i + C <= N; i++)
nways [i + C] += nways [i];
}
fprintf (fout, "%lld\n", nways [N]);
return 0;
}