HDU - 1059 Dividing

题意：求能否将总价值平分

思路：完全背包的做法

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;

int a[12],f[200002];
int sum;

int main(){
	int t = 1;
	while (scanf("%d%d%d%d%d%d",&a[1],&a[2],&a[3],&a[4],&a[5],&a[6]) != EOF && 
			a[1]+a[2]+a[3]+a[4]+a[5]+a[6] != 0){
		printf("Collection #%d:\n",t++);
		sum = a[1]+2*a[2]+3*a[3]+4*a[4]+5*a[5]+6*a[6];
		if (sum % 2 == 1){
			printf("Can‘t be divided.\n\n");
			continue;
		}
		int dir = sum / 2;
		memset(f,0,sizeof(f));
		for (int i = 1; i <= 6; i++)
			for (int k = 1; a[i]; k <<= 1){
				if (a[i] < k)
					k = a[i];
				for (int j = dir; j >= k*i; j--)
					if (f[j] < f[j-k*i]+k*i)
						f[j] = f[j-k*i] + k*i;
				a[i] -= k;
			}
		if (f[dir] == dir)
			printf("Can be divided.\n\n");
		else printf("Can‘t be divided.\n\n");
	}
	return 0;
}

HDU - 1059 Dividing,布布扣,bubuko.com

HDU - 1059 Dividing

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