题意
给出物品种类,物品单价,每种物品的数量,尽可能把其分成价值相等的两部分。
思路
背包的思路显然是用一半总价值当作背包容量。
生成函数则是构造形如$1+x^{w[i]}+x^{2*w[i]}+...+x^{num[i]*w[i]}$的多项式,找到离$sum/2$最近的就完事。
代码
#include <bits/stdc++.h> #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; }