| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
求大侠看看,2进制多重背包,死活过不了#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator