设为首页 加入收藏

TOP

HDU OJ Dividing 题目1059
2015-11-21 00:56:16 来源: 作者: 【 】 浏览:1
Tags:HDU 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;
}

?

】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
分享到: 
上一篇HDU 3987 Harry Potter and the F.. 下一篇HDU - 4289 Control (最小割 MCMF)

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容: