HDU OJ Dividing 标题1059

HDU OJ Dividing 题目1059

多重背包问题

#include <iostream>
#include <string.h>
#include <stdio.h>
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<n)
{
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:\nCan't be divided.\n\n",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:\nCan be divided.\n\n",num);
else printf("Collection #%d:\nCan't be divided.\n\n",num);
num++;
}
return 0;
}