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

求大侠看看,2进制多重背包,死活过不了

Posted by 2006011312 at 2013-06-22 08:19:34 on Problem 1014
#include<iostream>
#include<cmath>
using namespace std;

int num[6];

int main(){
	int index = 1;
	int status[120001] = {0}; 
	while(1)
	{
		int total = 0;
		for (int i = 0; i < 6 ; i++)
		{
			cin>>num[i];
			total += num[i]*(i+1);
		}		
		if (total == 0)
		{
			break;
		}
		cout<<"Collection #"<<index++<<":"<<endl;
		if(total %2 != 0)
		{
			cout<<"Can't be divided."<<endl<<endl;
			continue;
		}
		total /= 2;
		memset(status, 0, total*sizeof(int));
		for (int i = 0; i <= total; i++)
		{
			if (i <= num[0])
			{
				status[i] = 1;			
			}
			else
			{
				status[i] = 0;
			}
		}

		for (int i = 1; i < 6; i++)
		{
			int k = log(num[i]+1.0) / log(2.0);
			for (int j = 0; j <= k; j++)
			{
				for (int sum = total; sum >= 0; sum--)
				{
					int temp;
					if (j < k)
					{
						temp = sum-(i+1)*(int)pow(2.0, j);
					}
					else
					{
						temp = sum - (i+1)*(num[i] - (int)pow(2.0, j) + 1);
					}
					if (status[sum] == 0 && temp >= 0) 
					{
						status[sum] = status[temp];
					}
					if (sum == total && i == 5 && j == k)
					{
						break;
					}
				}
			}
		}
		
		if (status[total] == 1)
		{
			cout<<"Can be divied."<<endl;
		}
		else
		{
			cout<<"Can't be divided."<<endl;
		}
		cout<<endl;
	}
	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