【文件属性】：
文件名称：0-1背包分支限界法
文件大小：238KB
文件格式：RAR
更新时间：2014-01-01 08:00:07
0-1背包分支限界法
0int bbKnapsack()
{
int i=1;
int bestp=0;
double up=bound(1);
num=1;
while(i!=n+1)
{
if(cw+element[i].w<=C)
{
if(cp+element[i].val>bestp)
bestp=cp+element[i].val;
QueueEle queueEle;
queueEle.flag=1;
queueEle.profit=cp+element[i].val;
queueEle.upperProfit=up;
queueEle.weight=cw+element[i].w;
queueEle.level=i+1;;
queueEle.num=num*2;
q.push(queueEle);
}
up=bound(i+1);
if(up>=bestp)
{
QueueEle queueEle;
queueEle.flag=0;
queueEle.profit=cp;
queueEle.upperProfit=up;
queueEle.weight=cw;
queueEle.level=i+1;
queueEle.num=num*2+1;
q.push(queueEle);
}
QueueEle queueEle=q.top();
q.pop();
cw=queueEle.weight;
cp=queueEle.profit;
up=queueEle.upperProfit;
i=queueEle.level;
num=queueEle.num;
}
return cp;
}
【文件预览】：
0-1背包问题
----test()
--------knap4.in(10KB)
--------knap8.in(51KB)
--------knap7.in(38KB)
--------knap6.in(19KB)
--------knap5.in(16KB)
--------knap9.in(70KB)
--------knap1.in(1KB)
--------knap3.in(5KB)
--------knap0.in(28B)
--------knap2.in(2KB)
--------knap10.in(220KB)
----0_1背包.cpp(2KB)
----answer()
--------knap10.out(68KB)
--------knap0.out(16B)
--------knap2.out(706B)
--------knap9.out(24KB)
--------knap3.out(2KB)
--------knap8.out(17KB)
--------knap5.out(6KB)
--------knap7.out(11KB)
--------knap6.out(7KB)
--------knap1.out(490B)
--------knap4.out(2KB)
----prog616.pdf(78KB)