DP---母函数
先由钱币兑换问题开始 http://acm.hdu.edu.cn/showproblem.php?pid=1284
Problem Description
在一个国家仅有1分，2分，3分硬币，将钱N兑换成硬币有很多种兑法。请你编程序计算出共有多少种兑法。
Input
每行只有一个正整数N，N小于32768。
Output
对应每个输入，输出兑换方法数。
这道题有三种解法（参照此博客http://www.cnblogs.com/Findxiaoxun/p/3574907.html）
完全背包的解法很容易想到，模板性质的。
第二种技巧性的就会强一点。这样想，先只考虑1和3,不是1,就是3,全1的只有一种;每三个1就可以兑换一个3,方法数就有n/3种。再考虑2的情况，全部是2和1的情况，实际上，去掉i个3,就可以变成只含有1和2的情况，而类似的，只含有1和2的情况，可以有(n-3*i)/2种，此时只需要把这些方法数加起来就可以了。
第三种就是母函数了，在此引用下这位大神的博客（http://www.wutianqi.com/?p=596），
Woo讲的很好了，尤其是算法归纳的过程，不过个人感觉少了对代码的分析，这里我毛遂自荐，来讲下我的理解: 大家在学习母函数的时候，一定要记住理解这样一句话：母函数算法其实就是模拟手算多项式乘法。
首先要看Woo的那篇文章，最重要的理解是：
① 、首先对c1初始化，由第一个表达式(1+x+x^2+..x^n)初始化，把质量从0到n的所有砝码都初始化为1.
② 、 i从2到n遍历，这里i就是指第i个表达式，上面给出的第二种母函数关系式里，每一个括号括起来的就是一个表达式。
③、j 从0到n遍历，这里j就是(前面i個表达式累乘的表达式)里第j个变量，(这里感谢一下seagg朋友给我指出的错误，大家可以看下留言处的讨论)。如(1+x)(1+x^2)(1+x^3)，j先指示的是1和x的系数，i=2执行完之后变为 （1+x+x^2+x^3）(1+x^3)，这时候j应该指示的是合并后的第一个括号的四个变量的系数。
④ 、 k表示的是第j个指数，所以k每次增i（因为第i个表达式的增量是i）。
⑤ 、把c2的值赋给c1,而把c2初始化为0，因为c2每次是从一个表达式中开始的。
Woo这里是根据题目来说的，而且，其实他的代码里Num那个地方，其实是有两种的，一般情况下。 来看下母式子： (1+x+x^2+x^3+x^4+..)(1+x^2+x^4++..)(1+x^3+x^6+..) 第一个括号指的是1分的，在拆分第一个括号的之前，1分的能够构成数m，那么c1[m]=1;如果是有a个1分的，那么1分一直a，c1[a]=1;然后开始拆分第一个括号，就是把第一个括号和第二个括号合并，我们手算多项式乘法，先按括号一的那个1，乘(第二个括号里的内容)，很自然的c2[i]+=c1[i],这里的c2[i]表示的是在这次的循环过程中，中间的结果，这句话理解不了的话，继续看。然后括号一的第二个元素x，x*(....)=x*1+x*x^2+x*x^4...=x+x^3+x^5...最终，它们会和第一次乘出来的结果同项合并，x^3+x^3=2*x^3,其他值都类似，那么，c2[3]+=c1[1];c1[i]就是保存的之前乘出来的x^i结果的系数，等这一次乘完，c2[i]保存了最终的结果，那就把它的值都转移到c1里面去，然后c2又空。继续分解括号。
举个例子：
3个1分的硬币，1个2分的，2个3分的。
(1+x+x^2+x^3)(1+x^2)(1+x^3+x^6)
1.初始化：
0 1 2 3 4 5 6 7 8 9
c1: 1 1 1 1 0 0 0 0 0 0
C2全0
2.对第一个括号的1*(1+x^2),(i=2,j=0)得到
0 1 2 3 4 5 6 7 8 9
C2: 1 0 1 0 0 0 0 0 0 0
就是说，原来2个1可以组成2,现在，一个2就能替换，有1种方法。
3. X*(1+x^2) (i=2;j=1)
0 1 2 3 4 5 6 7 8 9
C2: 1 1 1 1 0 0 0 0 0 0
4. X^2*(1+x^2) j=2
0 1 2 3 4 5 6 7 8 9
C2: 1 1 2 1 0 0 0 0 0 0
5. x^3*(1+x^2) j=3
0 1 2 3 4 5 6 7 8 9
C2:1 1 2 2 0 0 0 0 0 0
把c2的值全都转移到c1里 i=3
剩下的步骤也是如此。
就是模拟手工计算多项式乘法。
Woo的博客介绍的几道题都挺不错，现在外面来把这个算法真正的理解运用下：
HDU1711，题意就是说，给价值不同的一些物品，让你把它们分成和尽可能接近的两堆。
一种很巧妙的思路是，转换成完全背包，或者是01背包。因为动态规划解决的问题一般是最××的问题，最多，最少，最接近，等等。而这个题，可以看成是sum/2空间的背包，让你用那些物品装，尽可能装满。背包的代码我先附上，背包专辑我后续我会整理出来。
#include<cstdio>
#include
<algorithm>
#include
<cstring>
using
namespace
std;
const
int
maxn=
5005
;
const
int
maxm=
255555
;
int
n,t,sum;
int
dp[maxm],v[maxn];
int
main(){
while
(scanf(
"
%d
"
,&t)&&t>
0
){
int
a,b;
n
=
0
;sum=
0
;
memset(v,
0
,
sizeof
(v));
for
(
int
i=
0
;i<t;i++
){
scanf(
"
%d%d
"
,&a,&
b);
while
(b--
){
v[n
++]=a;
//
wa
sum+=
a;
}
}
int
sum2=sum/
2
;
memset(dp,
0
,
sizeof
(dp));
for
(
int
i=
0
;i<n;i++
){
for
(
int
j=sum2;j>=v[i];j--
){
dp[j]
=max(dp[j],dp[j-v[i]]+
v[i]);
}
}
//
for(int i=0;i<=sum2;i++)printf("%d ",dp[i]);
int
ans=max(dp[sum2],sum-
dp[sum2]);
printf(
"
%d %d\n
"
,ans,sum-
ans);
}
return
0
;
}
再来看母函数的思路。可以这样想，因为题中对价值的限制为50,也就是说，只有50种值，有50种面值个数不同的硬币，要你求出，能表示出的最接近总数一半的那个值。转换为了母函数问题。来看i,j,k 50种面值，1的可以直接先处理，那么i=2 to 50，而j的范围就是0 to sum，k则是(k=0;k+j<=sum&& k<i*num[i];k+=i)k的限制也很好理解，因为只有num[i]个i面值的硬币，则多项式最多就能乘到x^(i*num[i])。
#include<cstdio>
#include
<cstring>
#include
<algorithm>
using
namespace
std;
int
c1[
250005
],c2[
250005
];
int
data[
51
];
int
sum;
int
main(){
int
n;
while
(scanf(
"
%d
"
,&n)&&n>
0
){
sum
=
0
;
int
a,b;
memset(data,
0
,
sizeof
(data));
memset(c1,
0
,
sizeof
(c1));
memset(c2,
0
,
sizeof
(c2));
for
(
int
i=
0
;i<n;i++
){
scanf(
"
%d%d
"
,&a,&
b);
data[a]
=
b;
sum
+=a*
b;
}
for
(
int
i=
0
;i<=data[
1
];i++)c1[i]=
1
;
for
(
int
i=
2
;i<=
50
;i++
){
for
(
int
j=
0
;j<=sum;j++
){
for
(
int
k=
0
;j+k<=sum&&k<=i*data[i];k+=
i)
c2[j
+k]+=
c1[j];
}
for
(
int
j=
0
;j<=sum;j++
){
c1[j]
=c2[j];c2[j]=
0
;
}
}
int
x=sum/
2
;
while
(!c1[x]){x--
;}
int
ans=max(x,sum-
x);
printf(
"
%d %d\n
"
,ans,sum-
ans);
}
return
0
;
}
