moneysystems - codetrick
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).
The amount money to construct is N (1 <= N <= 10,000).
有v种币值和一个钱数n，问用给定币值可以有多少种方案构成n。
完全背包。有v种物品（v种币值），每种物品对应固定的费用（币值），背包的总容量为n（钱数），求有多少种情况能使背包恰好装满。
http://lsharemy.com/wordpress/index.php/csit/usaco-prob-money-systems/
http://sdjl.me/index.php/archives/97
Read full article from moneysystems - codetrick
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)
10http://lujunda.cn/2012/12/28/usacosection-2-3ac%E8%87%AA%E5%8A%A8%E6%9C%BA-money-systems/
有v种币值和一个钱数n，问用给定币值可以有多少种方案构成n。
完全背包。有v种物品（v种币值），每种物品对应固定的费用（币值），背包的总容量为n（钱数），求有多少种情况能使背包恰好装满。
int N,V;//N种物品，背包容量为V。int c[25];//c[]用来存储费用。long long f[10001];//f[i]总钱数为i时的最大方法数。 int main(){ freopen("money.in","r",stdin); freopen("money.out","w",stdout); memset(f,0,sizeof(f[0])); scanf("%d%d",&N,&V); for(int i=0;i<N;i++) scanf("%d",&c[i]); f[0]=1; for(int i=0;i<N;i++) for(int v=c[i];v<=V;v++) f[v]+=f[v-c[i]]; printf("%lld\n",f[V]);} for (int m = 0; m < V; m++) for (int n = 0; n <= N; n++) dp[n] += (n - v[m] >= 0 ? dp[n - v[m]] : 0);http://sdjl.me/index.php/archives/97
Read full article from moneysystems - codetrick
