JAVA关于背包问题求解

1、java 关于背包问题求解import java.awt.*;import java.awt.event.actionevent;import java.awt.event.actionlistener;import java.util.arraylist;import javax.swing.joptionpane;import javax.swing.*;public class beibao private jframe jiemian;private jlabel label1,label2,label3,label4;private jbutton button1,button2;p

2、rivate textfield text1,text2,text3;private jscrollpane js;private int capacity;private static int flag=0;static jtextarea area=new jtextarea();public void jiemian()jiemian =new jframe();jiemian.settitle( 背包问题展示);jiemian.setbounds(250, 250, 400,400);jiemian.setresizable(false);jiemian.setlayout(null)

3、;label1=new jlabel( 设定背包容量);text1=new textfield();label1.setbounds(10, 10, 100, 30);text1.setbounds(150, 10, 100, 30);label2=new jlabel(产生随机数个数);label3=new jlabel(随机数如下所示);text2=new textfield();text3=new textfield();label2.setbounds(10, 60, 200, 30);label3.setbounds(10, 100, 200, 30);text2.setbounds

4、(150, 60, 100, 30);text3.setbounds(10, 140, 380, 30);button1=new jbutton( 运行 );button2=new jbutton( 退出 ); button1.setbounds(300, 10, 70, 30); button2.setbounds(300, 60, 70, 30);label4=new jlabel( 结果如下 );label4.setbounds(10,170,100,30);area=new jtextarea();js=new jscrollpane(area);area.seteditable(fa

5、lse);js.setbounds(10, 200, 380, 150);label1.setfont(new font( label2.setfont(new font( label3.setfont(new font( label4.setfont(new font( button1.setfont(new font( button2.setfont(new font( text1.setfont(new font( text2.setfont(new font( text3.setfont(new font( area.setfont(new font(宋体,font.plain,14)

6、;宋体,font.plain,14);宋体,font.plain,14);宋体,font.plain,14);宋体 , font.plain, 14);宋体 , font.plain, 14);宋体 , font.plain, 16);宋体 , font.plain, 16);宋体 , font.plain, 16);宋体 , font.plain, 16);jiemian.add(label1);jiemian.add(label2);jiemian.add(label3);jiemian.add(label4);jiemian.add(button1);jiemian.add(button

7、2);jiemian.add(text1);jiemian.add(text2);jiemian.add(text3);jiemian.add(js);jiemian.setvisible(true);button1.addactionlistener(new actionlistener()public void actionperformed(actionevent e)capacity=integer.valueof(text1.gettext();if(!text1.gettext().equals()int num=integer.valueof(text2.gettext();in

8、t a=new intnum;for (int i = 0; i num; i+)ai = new integer(int) (math.random() * 20);string s=;/ 将随机数显示for(int i=0;inum;i+)if(i=0)s=new string(string.valueof(a0)+ );else s=new string(s+string.valueof(ai)+ );text3.settext(s);/int weight=new inta.length;/*for(int i=0;ia.length;i+)weighti=ai;for(int i=0

9、;ia.length;i+)system.out.print(weighti);*/select(capacity, a, 0, new inta.length);/system.out.println(capacity);if(flag=0)joptionpane.showmessagedialog(jiemian, 无解 );elsejoptionpane.showmessagedialog(jiemian, 请输入背包容量););button2.addactionlistener(new actionlistener()public void actionperformed(action

10、event e)system.exit(1););public static void main(string args) beibao b=new beibao();b.jiemian();intprivate static void select(int capacity, int weight, int index, knapsack) / 背包剩余容量为 0, 则直接打印背包if(capacity = 0) print(knapsack);return;/ 从起始位置开始寻找第一个可以选择的物品while(index weight.length & capacity = weight.

11、 length) return;/ 将问题化简为在剩下的物品中，找到符合重量的物品的两个子问题/1. 背包中含有index 位置的物品select(capacity, weight, index+1, knapsack.clone();/2. 背包中不含有index 位置的物品select(capacity - weightindex, weight, index+1, put(knapsack, weightindex);/ 将物品放入背包中private static int put(int knapsack, int n) int pos = -1;/ 找到背包中第一个数字为 0 的位置while(knapsack+pos 0);knapsackpos = n;return knapsack;/ 打印背包中的物品private static void print(int knapsack) area.settext(area.gettext()+ 组合 : );flag=1;/*for(int i=0;iknapsack.length;i+)system.out.print(knapsacki);*/for (int i=0;iknapsack.length;i+)