Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

果断多重背包

Posted by ACMore_txj at 2014-04-05 23:18:26 on Problem 1014
//若质量总和v为偶数,那么能均分的条件一定是多重背包组合能装满v/2


#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int dp[120005] = {0};
int main()
{
	int n[10] = {0},cnt = 1,i,k,j,v;
	while(1)
	{
		v = 0;
		for(i = 1;i <= 6;i ++)
		{
			cin>>n[i];
			v += n[i] * i;
		}
		if(!v)
			break;
		if(v % 2)
			printf("Collection #%d:\nCan't be divided.\n\n",cnt);
		else
		{
			memset(dp,0,sizeof(dp));
			v /= 2;
			for(i = 1;i <= 6;i ++)
			{
				k = 1;
				while(n[i] > k)
				{
					for(j = v;j >= k * i;j --)
						dp[j] = max(dp[j],dp[j-k*i] + k * i);
					n[i] -= k;
					k *= 2;
				}
				for(j = v;j >= n[i] * i;j --)
					dp[j] = max(dp[j],dp[j-n[i]*i] + n[i] * i);
			}
			if(dp[v] == v)
				printf("Collection #%d:\nCan be divided.\n\n",cnt);
			else
				printf("Collection #%d:\nCan't be divided.\n\n",cnt);
		}
		cnt ++;
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator