
求能装入大小为sum/2的背包的最大价值
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <sstream>
#include <string>
#include <cstring>
#include <algorithm>
#include <iostream>
#define maxn 1005
#define INF 0x7fffffff
#define inf 10000000
#define MOD 1000000007
#define ull unsigned long long
#define ll long long
using namespace std; int v[maxn], m[maxn], n, dp[maxn*maxn]; int main() {
while(scanf("%d", &n) == 1 && n >= 0) {
int sum = 0;
memset(dp, 0, sizeof(dp));
for(int i = 0; i < n; ++ i) {
scanf("%d%d", &v[i], &m[i]);
sum += v[i]*m[i];
}
for(int i = 0; i < n; ++ i) {
for(int j = 1; j <= m[i]; ++ j) {
for(int k = sum/2; k >= v[i]*j; -- k) {
dp[k] = max(dp[k], dp[k-v[i]]+v[i]);
}
}
}
printf("%d %d\n", max(dp[sum/2], sum-dp[sum/2]), min(dp[sum/2], sum-dp[sum/2]));
}
return 0;
}