?

题意：有n种物品，给出每种物品的价值和数目，要将这些物品尽可能的分成相等的两份A和B且A>=B ,输出A，B。

?

母函数可以过，但感觉最直接的方法应该是多重背包。

母函数的话，也是按总价值的一半求，从一半到小枚举，直到找到系数不为0的就是B。

?

?

#include 
  
   
#include 
   
     #include
    
   
  

?

多重背包，按总价值的一半进行背包，相比母函数时间更快，一维的相比二维的时间更快。

未优化的多重背包：

?

?

#include 
  
   
#include 
   
     #include 
    
      using namespace std; int val[55],num[55]; int dp[125010]; int n; int main() { while(~scanf(%d,&n)) { if(n < 0) break; int sum = 0; for(int i = 1; i <= n; i++) { scanf(%d %d,&val[i],&num[i]); sum += val[i]*num[i]; } int tmp = sum/2; memset(dp,0,sizeof(dp)); dp[0] = 1; int ans = -1; for(int i = 1; i <= n; i++) { for(int j = 0; j <= num[i]; j++) { for(int v = tmp; v >= j*val[i]; v--) //逆序 if(dp[v-j*val[i]]) { dp[v] = 1; ans = max(ans,v); } } } printf(%d %d ,sum-ans,ans); } return 0; } 
    
   
  

?