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.set

3、Layout(null);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);la

4、bel3.setBounds(10, 100, 200, 30);text2.setBounds(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.setBou

5、nds(10,170,100,30);area=new JTextArea();js=new JScrollPane(area);area.setEditable(false);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 Fon

6、t(" text1.setFont(new Font(" text2.setFont(new Font(" text3.setFont(new Font(" area.setFont(new Font("宋體",Font.PLAIN,14);宋體",Font.PLAIN,14);宋體",Font.PLAIN,14);宋體",Font.PLAIN,14);宋體 ", Font.PLAIN, 14);宋體 ", Font.PLAIN, 14);宋體 ", Font.PLAIN,

7、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(button2);jiemian.add(text1);jiemian.add(text2);jiemian.add(text3);jiemian.add(js);jiemian.setVisible(t

8、rue);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;for (int i = 0; i <num; i+)ai = new Integer(int) (Math.random() *

9、20);String s=""/ 將隨機數顯示for(int i=0;i<num;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;i<a.length;i+)weighti=ai;for(int i=0;i<a.length;i+)System.out.print(we

10、ighti);*/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)

11、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 <

12、; weightindex)index+;/ 當沒有物品可以選擇，則退出if(index >= weight. 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

13、 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;i<knapsack.length;i+)System.out.print(knapsacki);*/for (int i=0;i<knapsack.length;i+) if (knapsacki=0