多重背包，每個物品有數(shù)量上限限制。沒有用二進制優(yōu)化。
#include <stdio.h>
#include <string.h>
#define N 250005
#define MAX(a, b) (a > b ? a : b)
int c[N];
int main()
{
int n, v[55], m[55], sum;
while(scanf("%d", &n), n >= 0)
{
sum = 0;
for(int i = 0; i < n; i++)
{
scanf("%d %d", &v[i], &m[i]);
sum += v[i] * m[i];
}
memset(c, 0, sizeof(c));
for(int i = 0; i < n; i++)
{
while(m[i]--)
{
for(int j = sum / 2; j >= v[i]; j--)
{
c[j] = MAX(c[j], c[j - v[i]] + v[i]);
}
}
}
n = MAX(c[sum / 2], sum - c[sum / 2]);
printf("%d %d\n", n, sum - n);
}
return 0;
}