首页 > itarticle > generating function with constrains

generating function with constrains

admin 11月 12, 2020 0

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
 
// Author：Call偶围城  
#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 () {
	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("%dn", 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偶围城  
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("%dn", sum);
	}
	return 0;
}
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能