hdu 1059 Dividing(优化的多重背包 可达可不达)

http://acm.hdu.edu.cn/showproblem.php?pid=1059

题意：有六种marbles，第i种marbles的价值为i，数量为输入的num[i]，两个人想按这些marbles的总价值平分，问他们是否能够平分成功.

思路：和hdu 1171 http://acm.hdu.edu.cn/showproblem.php?pid=1171 类似。能不能平分，可以按总价值的一半进行多重背包，若总价值一半能够到达，说明平分成功，不过这里需要进行优化。直接转化为01背包，TLE。。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

int dp[60010],use[60010],sum;
int num[10];
//优化的多重背包
void solve()
{
	sum = sum>>1;
	memset(dp,0,sizeof(dp));
	dp[0] = 1;

	for(int i = 1; i <= 6; i++)
	{
		if(num[i] > 0)
		{
			memset(use,0,sizeof(use));
			for(int j = i; j <= sum; j++)
			{
				if(dp[j-i] && !dp[j] && use[j-i] < num[i])
				{
					dp[j] = 1;
					use[j] = use[j-i]+1;
				}
			}
		}
	}

	if(dp[sum]) printf("Can be divided.\n\n");
	else printf("Can‘t be divided.\n\n");
}

int main()
{
	int item = 1;
	while(~scanf("%d %d %d %d %d %d",&num[1],&num[2],&num[3],&num[4],&num[5],&num[6]))
	{
		if(num[1]==0&&num[2]==0&&num[3]==0&&num[4]==0&&num[5]==0&&num[6]==0) break;

		sum = 0;
		for(int i = 1; i <= 6; i++)
			sum += num[i]*i;
		if(sum%2 != 0)
		{
			printf("Collection #%d:\nCan‘t be divided.\n\n",item++);
			continue;
		}
		else
		{
			printf("Collection #%d:\n",item++);
			solve();
		}


	}
	return 0;
}

hdu 1059 Dividing(优化的多重背包 可达可不达)

原文：http://blog.csdn.net/u013081425/article/details/19838357