Generating Function Implements：Credits Combination

发表于   |   分类于   |  

Problem

Statistics the number of conbination that can achieve n credits.

Input Formal

The first line includes one integer represents the number of cases;
The first line in each case has two integers n， k， n represents the total credits you will learn and k represents the courses you can choose.Assuming that the courses with same credits have no differences;
each line of the k lines below has two integers, the first integer，a ， represents the credits of the course and the second integer， b， represents there are b courses with a credits that you can choose.

Implements

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
// Title：Generating Function
// Author：Call偶围城
#include <stdio.h>
#define MAXSCORE 40 
#define MAXSUB 8
int main() {
	int T;
	int n, kk;
	int a[MAXSUB], b[MAXSUB];
	int i, j, k;
	int c1[MAXSCORE+1], c2[MAXSCORE+1];
	scanf("%d", &T);
	while (T--) {
		scanf("%d%d", &n, &kk);
		for (i = 0;i <= MAXSCORE;i++)
			c1[i] = c2[i] = 0;
		for (i = 0;i < kk;i++)
			scanf("%d%d", &a[i], &b[i]);
		for (i = 0;i <= a[0]*b[0] && i <= n;i+=a[0])
			c1[i] = 1;
		for (i = 1;i < kk;i++) {
			for (j = 0;j <= n;j++)
				for (k = 0;k <= a[i]*b[i] && k+j <= n;k+=a[i])
					c2[k+j] += c1[j];
			for (j = 0;j <= n;j++) {
				c1[j] = c2[j];
				c2[j] = 0;
			}
		}
		printf("%d\n", c1[n]);
	}
	return 0;
}

Sample

Input：
2
2 2
1 2
2 1
40 8
1 1
2 2
3 2
4 2
5 8
6 9
7 6
8 8

Output：
2
445

Traditional Method

// Title：Enumeration
// Author：Call偶围城

#include <stdio.h>

#define MAX 8

int main() {
    int T;
    int n, k;
    int a[MAX], b[MAX];
    int cnt;

    int i, j;
    int x0, x1, x2, x3, x4, x5, x6, x7;

    scanf("%d", &T);
    while (T--) {
        cnt = 0;

        scanf("%d%d", &n, &k);

        for (i = 0;i < k;i++)
            scanf("%d%d", &a[i], &b[i]);

        for (i = k;i < MAX;i++)
            a[i] = b[i] = 0;

        for (x0 = 0;x0 <= b[0];x0++)
            for(x1 = 0;x1 <= b[1];x1++)
                for (x2 = 0;x2 <= b[2];x2++)
                    for (x3 = 0;x3 <= b[3];x3++)
                        for (x4 = 0;x4 <= b[4];x4++)
                            for (x5 = 0;x5 <= b[5];x5++)
                                for (x6 = 0;x6 <= b[6];x6++)
                                    for (x7 = 0;x7 <= b[7];x7++) {
                                        if (x0*a[0]+x1*a[1]+x2*a[2]+x3*a[3]+x4*a[4]+x5*a[5]+x6*a[6]+x7*a[7] == n)
                                            cnt++;
                                    }

        printf("%d\n", cnt);
    }

    return 0;
}