HDU - 1171 Big Event in HDU

题意：给你n个物品，每个物品有价值和数量，让你尽量平分总价格，第一个数要大于第二个

思路：做出类似的，从中间开始01背包

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
const int MAXN = 110;

int n,sum,a[MAXN<<3];
int f[300010];
int num;

int main(){
	while (scanf("%d",&n) != EOF && n > 0){
		num = 0,sum = 0;
		for (int i = 1;  i <= n; i++){
			int val,m;
			scanf("%d%d",&val,&m);
			sum += val * m;
			for (int j = 1; j <= m; j++)
				a[++num] = val;
		}
		int dir = sum / 2;
		memset(f,0,sizeof(f));
		for (int i = 1; i <= num; i++)
			for (int j = dir; j >= a[i]; j--)
				f[j] = max(f[j],f[j-a[i]]+a[i]);
		printf("%d %d\n",sum-f[dir],f[dir]);
	}
	return 0;
}

HDU - 1171 Big Event in HDU,布布扣,bubuko.com

HDU - 1171 Big Event in HDU

原文：http://blog.csdn.net/u011345136/article/details/21022765