Money Systems
The cows have not only created their own government but they have chosen to create their own money system. In their own rebellious way, they are curious about values of coinage. Traditionally, coins come in values like 1, 5, 10, 20 or 25, 50, and 100 units, sometimes with a 2 unit coin thrown in for good measure.
The cows want to know how many different ways it is possible to dispense a certain amount of money using various coin systems. For instance, using a system of {1, 2, 5, 10, ...} it is possible to create 18 units several different ways, including: 18x1, 9x2, 8x2+2x1, 3x5+2+1, and many others.
Write a program to compute how many ways to construct a given amount of money using supplied coinage. It is guaranteed that the total will fit into both a signed long long (C/C++) and Int64 (Free Pascal).
PROGRAM NAME: money
INPUT FORMAT
The number of coins in the system is V (1 <= V <= 25).
The amount money to construct is N (1 <= N <= 10,000).
| Line 1: |
Two integers, V and N |
| Lines 2..: |
V integers that represent the available coins (no particular number of integers per line) |
SAMPLE INPUT (file money.in)
3 10
1 2 5
OUTPUT FORMAT
A single line containing the total number of ways to construct N money units using V coins.
SAMPLE OUTPUT (file money.out)
10
Analysis
It is really a very good problem to train your dynamic programing skill. Initially, it is close to the comletement pack problem. The only difference is that we need to calculate the methods instead of the highest value. But it doesn't matter, change the traditional function max into a proper one: sum.Well, the problem becomes simple.
Here I'd better provode my dynamic function: f[i][v]=sum{f[i-1][v-k*w[i]]|0<=k*w[i]<=N}
The f[i][v] stands for the ith coin for you to choose and v is the money you need to express. Of course, k is the number of the coins. Wow,fantastic!
Code
/**//*
ID:braytay1
PROG:money
LANG:C++
*/
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
ofstream fout("money.out");
ifstream fin("money.in");
void swap(int *p1,int *p2)
{
int tmp;
tmp=*p1;
*p1=*p2;
*p2=tmp;
}
int partition(int a[],int p,int r)
{
int x,i;
x=a[r];
i=p-1;
for (int j=p;j<r;j++)
{
if (a[j]<=x) {i++;swap(a+i,a+j);}
}
swap(a+i+1,a+r);
return i+1;
}
void quicksort(int a[],int p,int r)
{
if (p<r)
{
int q;
q=partition(a,p,r);
quicksort(a,p,q-1);
quicksort(a,q+1,r);
}
}
int main(){
int V,N;
fin>>V>>N;
int w[26];
long long int f[10001],g[10001];
for(int i=1;i<=V;i++){
fin>>w[i];
}
quicksort(w,1,V);
memset(f,0,sizeof(f));
memset(g,0,sizeof(g));
for (int i=0;i*w[1]<=N;i++) g[i*w[1]]=1;
for(int i=2;i<=V;i++){
for(int j=0;j<=N;j++){
for(int k=0;k*w[i]<=j;k++){
f[j]+=g[j-k*w[i]];
}
}
for(int j1=0;j1<=N;j1++){
g[j1]=f[j1];
f[j1]=0;
}
}
fout<<g[N]<<endl;
return 0;
}