文件名称：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)