Money Systems（DP）

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（1 ~ 25），N（1 ~ 10000），代表有 V 种货币，N 的钱数，后给出这 V 种货币，每种货币的提供量无限。输出有多少凑钱数的方法刚好达到 N 这么多钱。

 

    思路：

    DP。完全背包。

    设 dp[ i ][ j ] 代表当选择第 i 种钱币时，凑足 j 元钱的方法数。同0，1背包的思路相似，每种钱币都有两种选择情况，选或者不选。

    选：设 k 代表可以选择 k 张 i 的钱币，所以 dp [ i ][ j ] += dp [ i - 1 ][ j - k * mon[ i ] ] ；

    不选：dp [ i ][ j ] += dp [ i - 1 ][ j ] ；

    循环 K 的时候从0开始即可以两种都一起考虑到了，因为 0 即代表不选。 注意方法数用 long long 即可。

 

    AC：

/*
TASK:money
LANG:C++
ID:sum-g1
*/
#include<stdio.h>
#include<string.h>
long long dp[30][10005];
int mon[30];

int main()
{
    freopen("money.in","r",stdin);
    freopen("money.out","w",stdout);
    int v,n;
    scanf("%d%d",&v,&n);
    memset(dp,0,sizeof(dp));
    for(int i = 0;i <= v;i++)   dp[i][0] = 1;
    for(int i = 1;i <= v;i++)
        scanf("%d",&mon[i]);
    for(int i = 1;i <= v;i++)
    {
        for(int j = 1;j <= n;j++)
        {
            for(int k = 0;k * mon[i] <= j;k++)
                dp[i][j] += dp[i - 1][j - k * mon[i]];
        }
    }
    printf("%lld\n",dp[v][n]);
}