Generating Function With Constrains

发表于   |   分类于   |  

Problem

There are five kinds of coins， valuing 1， 5， 10， 25， 50.Given a integer and use these five kinds of coins to conbine.Each kind of coins is infinit but the sum of coins to sum up the integer mustn’t exceeding 100.Futhermore, the given integer is smaller than 250.The question is that how many methods we can sum up the integer with the five kinds of coins.

Input Formal

There is one integer each line represents the value we want to sum up.

Implements

we should add one demension to record the number of methods in each condition with different num of coins and add a loop to limit the num of coins.
At the end of the program， we should sum up the num of methods with different num of coins but having the same value.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
// Title：Generating Function
// Author：Call偶围城  
#include <stdio.h>
#define POWER 250
#define MAX 100
#define NCOINS 5
int c1[POWER+1][MAX+1], c2[POWER+1][MAX+1];
int table[POWER+1];
const int coins[NCOINS+1] = {
	0, 1, 5, 10, 25, 50
};
void InitTable() {
	int i, j, k, u, v;
	for (i = 0;i <= POWER;i++) 
		for (j = 0;j <= MAX;j++)
			c1[i][j] = c2[i][j] = 0;
	c1[0][0] = 1;
	for (i = 1;i <= NCOINS;i++) { 
		for (j = 0;j <= POWER;j++) 
			for (k = 0;k*coins[i]+j <= POWER;k++)
				// constrains：the number of coins mustn't exceed 100
				for (u = 0;u+k <= MAX;u++)
					c2[j+k*coins[i]][k+u] += c1[j][u];
		for (j = 0;j <= POWER;j++) {
			for (k = 0;k <= MAX;k++) {
				c1[j][k] = c2[j][k];
				c2[j][k] = 0;
			}
		}
	}
	table[0] = 1;
	for (i = 1;i <= POWER;i++) {
		table[i] = 0;
		for (j = 0;j <= POWER;j++)
			table[i] += c1[i][j];
	}
}
int main() {
	int n;
	InitTable();
	while (scanf("%d", &n) != EOF) {
		printf("%d\n", table[n]);
	}
	return 0;
}

Samples

Inputs：
0
11
26
50
100
200
249
250

Outputs：
1
12
39
149
803
5135
7347
3830

Traditional Methods

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// Title：Enumeration
// Author：Call偶围城  
#include <stdio.h>
const int m[5] = {
	50, 25, 10, 5, 1
};
int main() {
	int n;
	int i, j, k, u, v;
	int sum;
	while (scanf("%d" ,&n) != EOF) {
		if (n != 0) {
			sum = 0;
			for (i = n/m[0];i >= 0;i--)
				for (j = (n-i*m[0])/m[1];j >= 0;j--)
					for (k = (n-i*m[0]-j*m[1])/m[2];k >= 0;k--)
						for (u = (n-i*m[0]-j*m[1]-k*m[2])/m[3];u >= 0;u--)
							if (i+j+k+u+(n-i*m[0]-j*m[1]-k*m[2]-u*m[3])/m[4] <= 100)
								sum++;
		}
		else
			sum = 1;
		printf("%d\n", sum);
	}
	return 0;
}