maxValue=CurrentValue;
System.out.println("1背包中物品的最大总价值为"+maxValue);
}
}
}
分支限界算法:
packagebag01b;
importjava.util.ArrayList;
publicclassbag01do{
publicstaticvoidmain(String[]args){
//TODOAuto-generatedmethodstub
ArrayList
objects.add(newobject(10,60));
objects.add(newobject(20,100));
objects.add(newobject(30,120));
bagb=newbag(50,objects);
b.findmaxvalue();
b.show();
}
}
-----------------------------------------------------------------------
packagebag01b;
importjava.util.ArrayList;
importjava.util.Collections;
importjava.util.PriorityQueue;
publicclassbag{
privateintbagv;
privateArrayList
privateintmaxvalue;
privateArrayList
publicbag(intv,ArrayList
super();
this.bagv=v;
this.objects=o;
this.maxvalue=0;
this.result_objects=null;
Collections.sort(objects);
}
publicvoidshow(){
System.out.println("maxvalue:
"+this.maxvalue);
System.out.println("theobjectwhenmaxvalue:
"+this.result_objects);
}
publicvoidfindmaxvalue(){
PriorityQueueenode=newPriorityQueue<>();
Nodenode=newNode(0,null,bagv,this.objects);
enode.offer(node);
while(true){
if(enode.isEmpty())
break;
node=enode.poll();
if(node.isend()){
this.maxvalue=node.get_bag_value();
this.result_objects=newArrayList<>(node.get_in_bag_object());
return;
}
inti=node.get_node_in();
objectiobject=this.objects.get(i);
if(node.get_bag_weight()+iobject.getweight()<=this.bagv){
ArrayList
newnodeinbag.add(iobject);
intnewnodebagv=node.get_bag_leftv()-iobject.getweight();
Nodenewnode=newNode(i+1,newnodeinbag,newnodebagv,this.objects);
enode.add(newnode);
if(newnode.get_bag_value()>this.maxvalue){
this.maxvalue=newnode.get_bag_value();
this.result_objects=newArrayList<>(newnode.get_in_bag_object());
}
}
Nodenewnode=newNode(i+1,node.get_in_bag_object(),node.get_bag_leftv(),this.objects);
if(newnode.get_bag_prio()>this.maxvalue)
enode.add(newnode);
}
}
}
-----------------------------------------------------------------------
packagebag01b;
importjava.util.ArrayList;
publicclassNodeimplementsComparable{
privateintnode_in;
privateArrayListinbag_object;
privateArrayListoutbag_object;
privateintleftv;
privateintprio;
publicNode(inti,ArrayListin,intl,ArrayListout){
super();
this.node_in=i;
if(in==null)
in=newArrayList<>();
this.inbag_object=in;
this.leftv=l;
this.outbag_object=out;
this.prio=this.find_prio();
}
privateintfind_prio(){
//TODOAuto-generatedmethodstub
intbag_left=this.leftv;
intp=this.get_bag_value();
inti=this.node_in;
objectiobject=null;
while(true){
if(i>=this.inbag_object.size())
break;
iobject=this.inbag_object.get(i);
if(iobject.getweight()>bag_left)
break;
bag_left-=iobject.getweight();
p+=iobject.getvalue();
i++;
}
if(i<=this.inbag_object.size()-1)
p+=iobject.getvw()*bag_left;
returnp;
}
publicintget_bag_weight(){
intw=0;
for(objecto:
this.inbag_object){
w+=o.getweight();
}
returnw;
}
publicintget_bag_value(){
intw=0;
for(objecto:
this.inbag_object){
w+=o.getvalue();
}
returnw;
}
@Override
publicintcompareTo(Nodeo){
//TODOAuto-generatedmethodstub
if(this.prio>o.prio)return-1;
if(this.prioreturn0;
}
publicbooleanisend(){
if(this.node_in==this.outbag_object.size())
returntrue;