Problem 14: Money Systems
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
题意：
给出v中硬币面值和总价钱N。计算能有多少种方法使得利用v中若干硬币组成N。
代码如下：
/*
LANG: C
TASK: money
*/
#include<stdio.h>
long long dp[26][10001];
int main()
{
freopen("money.in", "r", stdin);
freopen("money.out", "w", stdout);
int i, j, n, m, s[26];
scanf("%d%d", &n, &m);
for (i = 1; i <= n; i++)
{
scanf("%d", &s[i]);
}
for (i = 1; i <= n; i++)
{
dp[i][0] = 1;//取0元是可以的。
}
for (i = 1; i <= n; i++)//[i, j]表示在前i种硬币种能组成j元的情况个数
{
for (j = 1; j <= m; j++)
{
if (j - s[i] >= 0)
{
dp[i][j] = dp[i-1][j] + dp[i][j-s[i]];
}
else
{
dp[i][j] = dp[i-1][j];
}
}
}
printf("%lld\n", dp[n][m]);
fclose(stdin);
fclose(stdout);
//system("pause");
return 0;
}
由于每次计算dp[i][j] 都是利用到dp[i-1][j]和d[i][j-s[i]].而计算顺序是从左到右，从上到下。所以每次计算dp[i][j]时，两个前提条件都已被计算。
所以可以只用一维空间。
代码如下：
/*
LANG: C
TASK: money
*/
#include<stdio.h>
long long dp[10001];
int main()
{
freopen("money.in", "r", stdin);
freopen("money.out", "w", stdout);
int i, j, n, m, s[26];
scanf("%d%d", &n, &m);
for (i = 1; i <= n; i++)
{
scanf("%d", &s[i]);
}
dp[0] = 1;
for (i = 1; i <= n; i++)
{
for (j = 1; j <= m; j++)
{
if (j - s[i] >= 0)
{
dp[j] = dp[j] + dp[j-s[i]];
}
}
}
printf("%lld\n", dp[m]);
fclose(stdin);
fclose(stdout);
//system("pause");
return 0;
}