题意: 同样的学分 , 有多少种组合数, 注意同样学分, 课程没有区别
思路: 两种方法
背包
母函数
背包:
注意初始化时 dp[0]=1, 其他都为 0, 循环时从学分 N 开始更新, 减到为 0, 表示成功, 组合数加一.
代码:
- #include <iostream>
- using namespace std;
- int main ()
- {
- int t,n,m,i,j,k,l,a,b,dp[55]; //dp 记录当前学分的组合数
- cin>>t;
- while(t--&&cin>>n>>m)
- {
- for(i=dp[0]=1;i<55;i++)
- dp[i]=0;
- while(m--&&cin>>a>>b)
- {
- for(i=n;i>=a;i--) // 从最终的学分向前更新
- for(j=1;j<=b;j++) // 选择 1 到 b 门课
- if(j*a<=i) // 学分不过界
- dp[i]+=dp[i-j*a]; // 那就把他加起来
- }
- cout<<dp[n]<<endl;
- }
- }
母函数:
母函数的基本知识:
通过例题来了解:
例一:
有 1 克, 2 克, 3 克, 4 克的砝码各一枚, 能称出哪几种重量? 每种重量各有几种可能方案?
考虑用母函数来解决这个问题:
我们假设 x 表示砝码, x 的指数表示砝码的重量, 这样:
个 1 克的砝码可以用函数 1+1*x^1 表示,(1 其实应该写为: 1*x^0, 即 1 代表重量为 2 的砝码数量为 0 个.)
1 个 2 克的砝码可以用函数 1+1*x^2 表示,
1 个 3 克的砝码可以用函数 1+1*x^3 表示,
1 个 4 克的砝码可以用函数 1+1*x^4 表示,
这里的系数表示状态数 (方案数)
几种砝码的组合可以称重的情况, 可以用以上几个函数的乘积表示:
- (1+x)(1+x^2)(1+x^3)(1+x^4)
- =(1+x+x^2+x^4)(1+x^3+^4+x^7)
- =1 + x + x^2 + 2*x^3 + 2*x^4 + 2*x^5 + 2*x^6 + 2*x^7 + x^8 + x^9 + x^10
从上面的函数知道: 可称出从 1 克到 10 克, 系数便是方案数.(!!! 经典!!!)
例如右端有 2^x^5 项, 即称出 5 克的方案有 2 种: 5=3+2=4+1; 同样, 6=1+2+3=4+2;10=1+2+3+4.
故称出 6 克的方案数有 2 种, 称出 10 克的方案数有 1 种 .
例二:
求用 1 分, 2 分, 3 分的邮票贴出不同数值的方案数:
第一种每种是一个, 而这里每种是无限的.
g(x)=(1+x+x^2+...)(1+x^2+x^4...)(1+x^3+x^6+...)
以展开后的 x^4 为例, 其系数为 4, 即 4 拆分成 1,2,3 之和的拆分方案数为 4;
即 :4=1+1+1+1=1+1+2=1+3=2+2
这里再引出两个概念 "整数拆分" 和 "拆分数":
所谓整数拆分即把整数分解成若干整数的和 (相当于把 n 个无区别的球放到 n 个无标志的盒子, 盒子允许空, 也允许放多于一个球). 整数拆分成若干整数的和, 办法不一, 不同拆分法的总数叫做拆分数.
代码实现:
(1+x)(1+x^2)(1+x^3)(1+x^4)
我们要写的代码就是要计算上面的函数式相乘之后的结果, 数组 c1[] 存函数 G(x) 的每一项系数. 代码的实现方式是: 通过循环, 每次循环把前两个括号相乘, 得到新的第一个括号, 一直把所有的括号都乘完.
例如:(1+x)(1+x^2)(1+x^3)(1+x^4)
=(1+x+x^2+x^3)(1+x^3)(1+x^4)
这一步就实现了前两个括号融合成一个括号.
例二代码:
每种种类个数无限为例, 给出模板:
- #include <iostream>
- using namespace std;
- const int _max = 10001;
- // c1 是保存各项质量砝码可以组合的数目
- // c2 是中间量, 保存没一次的情况
- int c1[_max], c2[_max];
- int main()
- {
- int nNum; // 你想用已有的面值组成 nNum 大小的面值
- int i, j, k;
- // 该代码的前提是假设所有面值为 1,2,3,4,5..... 的连续数, 即下面的 i
- // 数量无限
- while(cin>> nNum)
- {
- for(i=0; i<=nNum; ++i) // 此时的 nNum 是第一个括号的所有项个数 // ----
- {
- c1[i] = 1;
- c2[i] = 0;
- }
- for(i=2; i<=nNum; ++i) //nNum 括号个数 // -----
- {
- for(j=0; j<=nNum; ++j) //j 是第一个括号里的每一项 x^j 的指数 j
- for(k=0; k+j<=nNum; k+=i) // k 是第二个括号的每一项 x^k 的指数
- {
- c2[j+k] += c1[j]; // 目前的第一括号与第二括号两两相乘
- // 由于第二括号的系数全为 1, 相乘后的系数就是 c1[j], 累加即可
- }
- for(j=0; j<=nNum; ++j) // 把 c2 中的值给 c1, 并把 c2 清 0
- {
- c1[j] = c2[j];
- c2[j] = 0;
- }
- }
- cout <<c1[nNum] << endl;// 输出能组成 nNum 大小的方案数
- }
- return 0;
- }
本题中每个学分的课程有限, 代码模板又不一样:
高效的母函数模板
https://blog.csdn.net/xiaofei_it/article/details/17042651
直接套模板就好:
代码:
- #include <iostream>
- #include <cstring>
- using namespace std;
- #define min(a,b) ((a)<(b)?(a):(b))
- int T,N,K,n[8],v[8],a[42],b[42],i,j,k,last,last2;
- int main()
- {
- cin>>T;
- while ((T--)!=0)
- {
- cin>>N>>K;
- for (i=0;i<K;i++)
- cin>>v[i]>>n[i];
- a[0]=1;
- last=0;
- for (i=0;i<K;i++)
- {
- last2=min(last+n[i]*v[i],N);
- memset(b,0,sizeof(int)*(last2+1));
- for (j=0;j<=n[i]&&j*v[i]<=last2;j++)
- for (k=0;k<=last&&k+j*v[i]<=last2;k++)
- b[k+j*v[i]]+=a[k];
- memcpy(a,b,sizeof(int)*(last2+1));
- last=last2;
- }
- cout<<a[N]<<endl;
- }
- return 0;
- }
注意数组的初始化
来源: http://www.bubuko.com/infodetail-2757051.html