| ||||||||||
| 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 | |||||||||
果断多重背包//若质量总和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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator