贪心算法JAVA-实现代码

贪心算法背包问题java代码packagetxsf;importjava.util.*;publicclassBag{publicintgetCapacity(){returncapacity;}publicvoidsetCapacity(intcapacity){this.capacity=capacity;}publicfloatgetValue(){returnvalue;}publicvoidsetValue(floatvalue){this.value=value+this.value;}privateintcapacity;//背包容量privatefloatvalue;//背包内价值privateRandomrand;publicBag(){//自动生成背包rand=newRandom();capacity=rand.nextInt(150);if(capacity50){capacity+=rand.nextInt(70);}System.out.println(背包容量:+capacity);value=0;}publicBag(intcapacity){//手工生成背包this.capacity=capacity;System.out.println(背包容量:+capacity);}publicfloatgetvalue(){returnvalue;}}/*abstractclassComputeItems{publicListItemslist=newArrayListItems();//public}*/classItems{privateStringimageStr;//物品名称privateintcapacity;//物品空间privateintvalue;//物品价值privateRandomrand;publicItems(Strings){//自动生成物品rand=newRandom();this.imageStr=s;this.value=rand.nextInt(50)+1;this.capacity=rand.nextInt(50)+1;System.out.println(s+:+this.capacity++this.value);}publicItems(Strings,intcapacity,intvalue){//手工生成物品this.imageStr=s;this.capacity=capacity;this.value=value;}publicfloatgetCapacity(){returnthis.capacity;}publicfloatgetValue(){returnthis.value;}publicStringgetimageStr(){returnthis.imageStr;}publicStringtoString(){return+imageStr+:容量为：+capacity+价值为：+value;}}interfaceCompute{float[]Sort();MapgetMap();}//重量优先计算classCapaimplementsCompute{privateListItemslist;privatefloat[]array;//排序物品权值privateMapFloat,ItemsmapItems;//哈希表，用来存放物品权值与物品publicCapa(Listlist){this.list=list;mapItems=newHashMapFloat,Items();array=newfloat[list.size()];}publicfloat[]Sort(){inti=0;for(Itemsitems:list){array[i++]=items.getCapacity();//将物品权重放入数组mapItems.put(items.getCapacity(),items);//将物品权重与物品对象放入map对象}Arrays.sort(array);//物品排序升序returnarray;}@OverridepublicMapgetMap(){//TODOAuto-generatedmethodstubreturnmapItems;}publicStringtoString(){return重量优先;}}//价值优先计算classValueimplementsCompute{privateListItemslist;privatefloat[]array;privateMapFloat,ItemsmapItems;publicValue(Listlist){this.list=list;mapItems=newHashMapFloat,Items();array=newfloat[list.size()];}publicfloat[]Sort(){inti=0;for(Itemsitems:list){array[i++]=items.getValue();mapItems.put(items.getValue(),items);}Arrays.sort(array);returnarray;}@OverridepublicMapgetMap(){//TODOAuto-generatedmethodstubreturnmapItems;}publicStringtoString(){return价值优先;}}//单位价值优先classPreValueimplementsCompute{privateListItemslist;privatefloat[]array;privateMapFloat,ItemsmapItems;publicPreValue(Listlist){this.list=list;mapItems=newHashMapFloat,Items();array=newfloat[list.size()];}publicfloat[]Sort(){inti=0;for(Itemsitems:list){floatf=items.getValue()/items.getCapacity();array[i++]=f;mapItems.put(f,items);}Arrays.sort(array);returnarray;}@OverridepublicMapgetMap(){//TODOAuto-generatedmethodstubreturnmapItems;}publicStringtoString(){return单位价值优先;}}//自定义优先classCustomFormimplementsCompute{privateListItemslist;privatefloat[]array;privateMapFloat,ItemsmapItems;floatf1,f2;publicCustomForm(ListItemslist,floatf1,floatf2){this.list=list;this.f1=f1;this.f2=f2;mapItems=newHashMapFloat,Items();array=newfloat[list.size()];System.out.println(+list.size());}publicfloat[]Sort(){inti=0;for(Itemsitems:list){floatf=f1*items.getCapacity()+f2*items.getValue();System.out.println(f);array[i++]=f;mapItems.put(f,items);}Arrays.sort(array);returnarray;}@OverridepublicMapgetMap(){//TODOAuto-generatedmethodstubreturnmapItems;}publicStringtoString(){return自定义优先级;}}classShow{privatestaticfloat[]array;privatestaticMapFloat,Itemsmap;//权值与物品对应哈希表privatestaticMapItems,Cardmapcard;//物品与JPanel对象对应哈希表privatestaticBagbag;//背包对象privateintcapacity;privatefloatvalue;publicShow(float[]array,Mapmap,Bagbag,Mapmapcard){this.array=array;this.map=map;this.bag=bag;this.mapcard=mapcard;capacity=bag.getCapacity();value=bag.getValue();}publicfloatpack(){System.out.println(装包结果为：);for(intj=array.length;j0;j--){Floatfx=array[j-1];Itemsitems=(Items)map.get(fx);//取对应物品权重值对应物品对象Cardc=(Card)mapcard.get(items);//权重值对应JPanel对象inti=capacity-(int)items.getCapacity();if(i0){System.out.println(1+items);c.Box.setSelected(true);capacity=(int)(capacity-items.getCapacity());value=items.getValue()+value;System.out.println(剩余空间：+capacity);}else{floatf1=capacity/items.getCapacity()*items.getValue();value=value+f1;c.Box.setSelected(true);System.out.println(2+items);System.out.println(剩余空间：+capacity);break;}System.out.println(剩余容量为：+capacity+当前价值为：+value);}System.out.println(剩余容量为：v+capacity+当前价值为：+value);returnvalue;}}packagetxsf;importjavax.swing.*;publicclassCardextendsJPanel{privateJTextFieldCata;privateJTextFieldValue;privateJLabelLabel;publicJCheckBoxBox;privateStringimage;privatefloatcatacity,value;publicCard(Stringimage,floatf,floatg){setBorder(newTitledBorder(UIManager.getBorder(TitledBorder.border),image,TitledBorder.LEADING,TitledBorder.TOP,null,null));setBounds(newRectangle(100,0,100,100));this.image=image;this.catacity=f;this.value=g;setLayout(null);Label=newJLabel(Newlabel);Label.setIcon(newImageIcon(./img/+image+.png));Label.setBounds(1,28,64,6