首页 > 代码库 > hdu 1171 Big Event in HDU(母函数)
hdu 1171 Big Event in HDU(母函数)
链接:hdu 1171
题意:这题可以理解为n种物品,每种物品的价值和数量已知,现要将总物品分为A,B两部分,
使得A,B的价值尽可能相等,且A>=B,求A,B的价值分别为多少
分析:这题可以用母函数的思想解,不过求的不是方案数,而是判断尽可能接近总价值的一半的方案是否存在.
也可以用背包思想,每种物品的价值和数量已知,可以将总价值的一半作为容量,求最大价值,也就最接近所求值了
注:数组要开的稍微大一点,否则可能WA
#include<stdio.h> #include<string.h> int c1[300010],c2[300010],w[300010],num[300010],n; void mhs(int m) { int i,j,k; memset(c1,0,sizeof(c1)); memset(c2,0,sizeof(c2)); for(i=0;i<=w[1]*num[1];i+=w[1]) //将第一种物品形成的情况初始化为1 c1[i]=1; for(i=2;i<=n;i++){ for(j=0;j<=m;j++) for(k=0;k<=w[i]*num[i]&&j+k<=m;k+=w[i]) c2[j+k]+=c1[j]; for(j=0;j<=m;j++){ c1[j]=c2[j]; c2[j]=0; } } } int main() { int m,i,s; while(scanf("%d",&n)!=EOF){ if(n<0) break; s=0; for(i=1;i<=n;i++){ scanf("%d%d",&w[i],&num[i]); //w数组表示i物品的价值,num数组表示i物品的数量 s+=w[i]*num[i]; //求出所有物品的总价值 } if(n==0){ //当物品为0时,A,B肯定都为0 printf("0 0\n"); continue; } m=s/2; mhs(m); //用母函数求s/2的方案情况 for(i=m;i>=0;i--) //求<=m最大的满足题意的值 if(c1[i]) break; printf("%d %d\n",s-i,i); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。