HDU OJ Dividing 題目1059

多重背包問題

#include
#include
#include
using namespace std;
int mar[7],f[120005],v,k;
void ZeroOnePack(int va,int c
{
for(int i = v ; i >= va; i--)
if(f[i-va]+c>f[i])
f[i] = f[i-va]+c;
}
void complatePack(int va,int c）
{
for(int i = va; i <= v; i++)
if(f[i-va]+c>f[i])
f[i] = f[i-va]+c;
}
void mutilPack(int va,int c,int n)
{
if(n*va>=v)
complatePack(va,c);
else
{
int count = 1;
while(count {
ZeroOnePack(count*va,count*c);
n -=count;
count =2*count;
}
ZeroOnePack(n*va,n*c);
}
}
int main()
{
int total,num=1;
while(1)
{
total = 0;
for(int i = 1; i<7;i++)
{
scanf(%d,&mar[i]);
total += i*mar[i];
}
if(total==0)break;
if(total%2)
{
printf(Collection #%d: Can't be divided. ,num);
num++;
continue;
}
v = total/2;
memset(f,0,sizeof(f));
for(int i=1;i<7;i++)
mutilPack(i,i,mar[i]);
if(f[v]==v) printf(Collection #%d: Can be divided. ,num);
else printf(Collection #%d: Can't be divided. ,num);
num++;
}
return 0;
}