JAVA 关于背包问题求解

JAVA关于背包问题求解importjava.awt.*;importjava.awt.event.ActionEvent;importjava.awt.event.ActionListener;importjava.util.ArrayList;importjavax.swing.JOptionPane;importjavax.swing.*;publicclassBeibao{privateJFramejiemian;privateJLabellabel1,label2,label3,label4;privateJButtonbutton1,button2;privateTextFieldtext1,text2,text3;privateJScrollPanejs;privateintcapacity;privatestaticintflag=0;staticJTextAreaarea=newJTextArea();publicvoidjiemian(){jiemian=newJFrame();jiemian.setTitle(背包问题展示);jiemian.setBounds(250,250,400,400);jiemian.setResizable(false);jiemian.setLayout(null);label1=newJLabel(设定背包容量);text1=newTextField();label1.setBounds(10,10,100,30);text1.setBounds(150,10,100,30);label2=newJLabel(产生随机数个数);label3=newJLabel(随机数如下所示);text2=newTextField();text3=newTextField();label2.setBounds(10,60,200,30);label3.setBounds(10,100,200,30);text2.setBounds(150,60,100,30);text3.setBounds(10,140,380,30);button1=newJButton(运行);button2=newJButton(退出);button1.setBounds(300,10,70,30);button2.setBounds(300,60,70,30);label4=newJLabel(结果如下);label4.setBounds(10,170,100,30);area=newJTextArea();js=newJScrollPane(area);area.setEditable(false);js.setBounds(10,200,380,150);label1.setFont(newFont(宋体,Font.PLAIN,14));label2.setFont(newFont(宋体,Font.PLAIN,14));label3.setFont(newFont(宋体,Font.PLAIN,14));label4.setFont(newFont(宋体,Font.PLAIN,14));button1.setFont(newFont(宋体,Font.PLAIN,14));button2.setFont(newFont(宋体,Font.PLAIN,14));text1.setFont(newFont(宋体,Font.PLAIN,16));text2.setFont(newFont(宋体,Font.PLAIN,16));text3.setFont(newFont(宋体,Font.PLAIN,16));area.setFont(newFont(宋体,Font.PLAIN,16));jiemian.add(label1);jiemian.add(label2);jiemian.add(label3);jiemian.add(label4);jiemian.add(button1);jiemian.add(button2);jiemian.add(text1);jiemian.add(text2);jiemian.add(text3);jiemian.add(js);jiemian.setVisible(true);button1.addActionListener(newActionListener(){publicvoidactionPerformed(ActionEvente){capacity=Integer.valueOf(text1.getText());if(!text1.getText().equals()){intnum=Integer.valueOf(text2.getText());int[]a=newint[num];for(inti=0;inum;i++)a[i]=newInteger((int)(Math.random()*20));Strings=;//将随机数显示for(inti=0;inum;i++){if(i==0){s=newString(String.valueOf(a[0])+);}else{s=newString(s+String.valueOf(a[i])+);}}text3.setText(s);//int[]weight=newint[a.length];/*for(inti=0;ia.length;i++){weight[i]=a[i];}for(inti=0;ia.length;i++){System.out.print(weight[i]);}*/select(capacity,a,0,newint[a.length]);//System.out.println(capacity);if(flag==0){JOptionPane.showMessageDialog(jiemian,无解);}}else{JOptionPane.showMessageDialog(jiemian,请输入背包容量);}}});button2.addActionListener(newActionListener(){publicvoidactionPerformed(ActionEvente){System.exit(1);}});}publicstaticvoidmain(String[]args){Beibaob=newBeibao();b.jiemian();}privatestaticvoidselect(intcapacity,int[]weight,intindex,int[]knapsack){//背包剩余容量为0,则直接打印背包if(capacity==0){print(knapsack);return;}//从起始位置开始寻找第一个可以选择的物品while(indexweight.length&&capacityweight[index])index++;//当没有物品可以选择，则退出if(index=weight.length)return;//将问题化简为在剩下的物品中，找到符合重量的物品的两个子问题//1.背包中含有index位置的物品select(capacity,weight,index+1,knapsack.clone());//2.背包中不含有index位置的物品select(capacity-weight[index],weight,index+1,put(knapsack,weight[index]));}//将物品放入背包中privatestaticint[]put(int[]knapsack,intn){intpos=-1;//找到背包中第一个数字为0的位置while(knapsack[++pos]0);knapsack[pos]=n;returnknapsack;}//打印背包中的物品privatestaticvoidprint(int[]knapsack){area.setText(area.getText()+组合:);flag=1;/*for(inti=0;iknapsack.length;i++){System.out.print(knapsack[i]);}*/for(inti=0;iknapsack.length;i++){if(knapsack[i]==0)continue;area.setText(area.getText()+knapsack[i]+);//System.out.print(rhweu);}area.setText(area.getText()+\n);}}