Sun Yat-sen University ACM 2014. Dairy Queen
1. 原题中文大意;
给出一个在 [1, 300] 之间的数字N。然后给出一个集合，这个集合中有C 个数字，C在[1, 8]之间。该集合中的每个数字在[1, 200]之间。问如何用这个集合中的数字组合（数字可以重复使用），使它们的总和等于N。
2. 解这种题毫不犹豫地想到用动态规划。
3. 设一个数组 ways[301]; ways[n]表示有多少种方法可以组合成和n。假设集合中只一个数字x。那么问题就非常简单，只能取n个该数字，和的集合为{x, 2x, 3x}，即ways[x]=1，ways[2x]=1, ways[3x]=1 ….。如果集合中有m数字，假设我们已经求得了用这m个数字的组合可以得到的和的数目存到了ways数组里。即对于m个数字，已求得 ways[1] = ?, ways[2] = ?, ways[3] = ? ….. Ways[300] = ?。 那么在此基础上，再加多一个数字，即 m+1个数字的情况会是如何呢。设新加入的这个数字的值是p，则应该是 ways[q] += ways[q-p]。（q > p）
4. 程序注释清单.
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
int main(int argc, char* argv[])
{
int N, C, coin; // N为题意中的N，C即题意中的C. coin作临时变量用，不解释，可见下面的代码。
int ways[301] = { 0 }; // 见第三部分的分析。
ways[0] = 1; // 没有实际意义。为了方便计算.
scanf("%d %d", &N, &C);
for ( int i = 0; i < C; i++)
{
scanf("%d", &coin);
for ( int j = coin; j <= N; j++ )
{
ways[j] += ways[j-coin]; // 见第3部分的分析.
}
}
printf("%d\n", ways[N]);
return 0;
}
5.时间复杂度，空间复杂度分析。
空间复杂度是确定的常数。时间复杂度是o(n). n为有多少种面值的硬币。
http://ykyi.net zausiu's blog
原题：
Description
Bessie, always in need of an income, has decided to leverage her dairy skills by taking a part-time job at the local Dairy Queen restaurant. She is running a special cash register (since she has hooves instead of fingers and thus requires special accommodation). Her job is making change for customers as they make a purchase.
As she was counting out 83 cents in change, she wondered: "How many ways can I count out 83 cents? I can use three quarters and eight pennies, seven dimes and three pennies, 83 pennies… there must be a zillion ways!"
How many different ways can one make change for N (1 ≤ N ≤ 300) cents using coins from a set of C (1 ≤ C ≤ 8) coins of supplied values C_i (1 ≤ C_i ≤ 200)? "Different" means differing counts of coins.
Thus, 8 cents can be made, in American currency, with 1 five-cent piece + 3 one-cent pieces and also with 8 one-cent pieces. Using 3 one-cent pieces + 1 five-cent piece is the same as 1 five-cent piece + 3 one-cent pieces, so one can create eight cents in just two different ways. Note that some coin systems are poor at making change and result in an answer of '0'.
Coin values in the input file are listed in descending order from largest to smallest. All coin values will be distinct.
Input
Line 1: Two space-separated integers: N and C
Lines 2..C+1: Line i+1 contains a single integer: C_i
Output
Line 1: A single line with a single integer that is the number of ways to create N cents of change using the supplied coins. The answer is guaranteed to fit into a signed 32-bit int
Sample Input
83 5 50 25 10 5 1
Sample Output
159
copyright ykyi.net