上网搜了一下这道题的解法，主要有两个方法，一种是采用母函数的方法，一种是采用0/1背包的方法。
先说一下母函数，即生成函数，做个比喻，母函数就是一个多项式前面的系数的一个整体的集合，而子函数就是这个多项式每一项前面的系数。主要用于解决组合问题，类似于钱币的组合问题。利用母函数解题时，首先要写出表达式，通常是多项式的乘积形式，类似于：(x^(v[K]*n1[K])+x^(v[K]*(n1[K]+1))+x^(v[K]*(n1[K]+2))+...+x^(v[K]*n2[K]))。
例如，对于有n种物品，如果第i种物品有ki个，我们可以列式n个项相乘 (x^0+x^1+...x^k1)*(x^0+x^1+...x^k2)*...*(x^0+x^1+...x^kn)，每一项表示对于第i件物品，可以有(x^0+x^1+...x^ki)中取法，【注意系数都为1，因为同种物品取i件，它的取法是1】多项相乘：因为取m件物品这件事实要分为对n种物品各取分别取1次【0~ki个】， 是组合计数的乘法原理， x^m 的系数是组合成m件物品的所有方案数
一、母函数解题的核心就是要找到：
k（对应具体问题中物品的种类数）、
v[i]（表示该乘积表达式第i个因子的权重，对应于具体问题的每个物品的价值或者权重）、
n1[i]（表示该乘积表达式第i个因子的起始系数，对应于具体问题中的每个物品的最少个数，即最少要取多少个）、
n2[i]（表示该乘积表达式第i个因子的终止系数，对应于具体问题中的每个物品的最多个数，即最多要取多少个）。
之后迭代计算，并将结果放在一个数组a中。其中a[i]表示权重为i的组合数。
二、母函数对应的具体题型：
主要是普通型母函数，主要用在组合和整数拆分问题上。
关于母函数的百度百科：http://baike.baidu.com/view/2415279.htm
三、模板
先贴一下我收集到的母函数模板：
模板一
1 //a为计算结果，b为中间结果。 2 int a[MAX],b[MAX]; 3 //初始化a 4 memset(a,0,sizeof(a)); 5 a[0]=1; 6 for (int i=1;i<=17;i++)//循环每个因子 7 { 8 memset(b,0,sizeof(b)); 9 for (int j=n1[i];j<=n2[i]&&j*v[i]<=P;j++)//循环每个因子的每一项 ，p为可能的最大指数 10 for (int k=0;k+j*v[i]<=P;k++)//循环a的每个项 11 b[k+j*v[i]]+=a[k];//把结果加到对应位 12 memcpy(a,b,sizeof(b));//b赋值给a 13 }
有一个last变量记录当前的最大指数，可以提高程序的效率：
模板二：
1 //初始化a，因为有last，所以这里无需初始化其他位 2 a[0]=1; 3 int last=0; 4 for (int i=0;i<K;i++) 5 { 6 int last2=min(last+n[i]*v[i],P);//计算下一次的last 7 memset(b,0,sizeof(int)*(last2+1));//只清空b[0..last2] 8 for (int j=n1[i];j<=n2[i]&&j*v[i]<=last2;j++)//这里是last2 9 for (int k=0;k<=last&&k+j*v[i]<=last2;k++)//这里一个是last，一个是last2 10 b[k+j*v[i]]+=a[k]; 11 memcpy(a,b,sizeof(int)*(last2+1));//b赋值给a，只赋值0..last2 12 last=last2;//更新last 13 }
因为刚刚接触到acm，最近做的事简单的背包专题，所以此处仅附上背包的思路和解法：
思路：将背包的容量定为所有物品总价值的一半，然后就是0/1背包问题，dp[half]中存储的就是较小的半份。其中，dp[j]表示选前i间物品时，预算为j时背包中装的最大总价值。
状态转移方程为：dp[j]=max{dp[j],dp[j-f[i].v]+f[i].v};
1 #include"iostream" 2 #include"stdio.h" 3 #include"algorithm" 4 #include"string.h" 5 #include"cmath" 6 #define mx 105 7 using namespace std; 8 int dp[300000];//注意dp数组的大小 9 struct node 10 { 11 int v; 12 int c; 13 }f[mx]; 14 bool cmp(const node a,const node b) 15 { 16 if(a.v!=b.v) return a.v<b.v; 17 } 18 int main() 19 { 20 int n,i,j,k; 21 while(cin>>n,n>0) 22 { 23 int sum=0,half; 24 for(i=0;i<n;i++) 25 { 26 cin>>f[i].v>>f[i].c; 27 sum+=f[i].v*f[i].c; 28 } 29 half=sum/2; 30 sort(f,f+n,cmp); 31 memset(dp,0,sizeof(dp)); 32 for(i=0;i<n;i++) 33 { 34 for(k=1;k<=f[i].c;k++) 35 { 36 for(j=half;j>=f[i].v;j--) 37 { 38 if(dp[j]<dp[j-f[i].v]+f[i].v) dp[j]=dp[j-f[i].v]+f[i].v; 39 } 40 } 41 } 42 cout<<sum-dp[half]<<' '<<dp[half]<<endl; 43 } 44 return 0; 45 }