题意

给出物品种类，物品单价，每种物品的数量，尽可能把其分成价值相等的两部分。

思路

背包的思路显然是用一半总价值当作背包容量。

生成函数则是构造形如$1+x^{w[i]}+x^{2*w[i]}+...+x^{num[i]*w[i]}$的多项式，找到离$sum/2$最近的就完事。

代码

#include 
     
      #define DBG(x) cerr << #x << " = " << x << endl;using namespace std;const int N = 300000 + 5;int n, w[N], num[N], c[2][N * 10];int main() {    while(~scanf("%d", &n) && n > 0) {        memset(c, 0, sizeof c);        int sum = 0, ysum = 0;;        for(int i = 1; i <= n; i++) {            scanf("%d%d", &w[i], &num[i]);            ysum += w[i] * num[i];            sum += w[i] * num[i];        }        sum /= 2;        for(int i = 0; i * w[1] <= sum && i <= num[1]; i++) c[1][i * w[1]] = 1;        for(int i = 2; i <= n; i++) {            for(int j = 0; j <= sum; j++) {                if(!c[1 - (i & 1)][j]) continue;                for(int k = 0; k <= w[i] * num[i] && j + k <= sum; k += w[i]) c[i & 1][j + k] += c[1 - (i & 1)][j];            }            for(int j = 0; j <= sum; j++) c[1 - (i & 1)][j] = 0;        }        int tmp = sum;        while(!c[n & 1][tmp]) tmp--;        printf("%d %d\n", max(tmp, ysum - tmp), min(tmp, ysum - tmp));    }    return 0;}