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(1

4、50, 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(false);js.se

5、tBounds(10, 200, 380, 150);label1.setFont(new Font(宋体, Font.PLAIN, 14);label2.setFont(new Font(宋体, Font.PLAIN, 14);label3.setFont(new Font(宋体, Font.PLAIN, 14);label4.setFont(new Font(宋体, Font.PLAIN, 14);button1.setFont(new Font(宋体, Font.PLAIN, 14);button2.setFont(new Font(宋体, Font.PLAIN, 14);text1.s

6、etFont(new Font(宋体, Font.PLAIN, 16);text2.setFont(new Font(宋体, Font.PLAIN, 16);text3.setFont(new Font(宋体, Font.PLAIN, 16);area.setFont(new Font(宋体, Font.PLAIN, 16);jiemian.add(label1);jiemian.add(label2);jiemian.add(label3);jiemian.add(label4);jiemian.add(button1);jiemian.add(button2);jiemian.add(te

7、xt1);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();int a=new intnum; f

8、or (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)+ );elses=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;ia.length;i+)Syst

9、em.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(ActionEvent e)System.exi

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

11、 /将问题化简为在剩下的物品中，找到符合重量的物品的两个子问题 /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