public class BackProblem {	public static void main(String[] args) {	new 	BackProblemJFrame("背包问题");	}}

import java.util.StringTokenizer;public class BackProblemArithmetic {	String backVolume,goodsVolume,goodsWorth;	String bestVolume,group =""; int groupGoodsVolume =0,groupGoodsWorth=0;    BackProblemArithmetic(){		}        //数据有效性的判断	public boolean isNumber(String  backVolume, String goodsVolume,String goodsWorth){		boolean effective;		this.backVolume  = backVolume;		this.goodsVolume = goodsVolume;		this.goodsWorth  = goodsWorth;		//判断背包的容量输入是否有误		try{			Integer.valueOf(this.backVolume);		}		catch(Exception ex){			return	effective = false;		}		//物品的价值和物品的质量有效性的判断		String str = this.goodsVolume+","+this.goodsWorth;		if (!this.backVolume.equals("") && !this.goodsVolume.equals("")				&& !this.goodsWorth.equals("")) {			StringTokenizer tokenizer = new StringTokenizer(str, "，, ");			effective = true;			while (tokenizer.hasMoreTokens()) {				try {					Integer.valueOf(tokenizer.nextToken());				} catch (Exception e) {					 effective = false;				}			}		    //判断物品的价值和物品的质量个数是否一致			tokenizer = new StringTokenizer(this.goodsVolume, "，, ");			int a = tokenizer.countTokens();			tokenizer = new StringTokenizer(this.goodsWorth, "，, ");			int b = tokenizer.countTokens();	        if(a!= b)	effective = false;		        		}		else effective  = false;	    return effective;	}    //背包算法的调用	public void backAnswer(){		int gv[],gw[];//定义数组用于存取goodVolume 和 goodsWorth 的值		int i = 1,c = 0,num = 0;//c背包的容量 ， num 背包中物品的个数 		//解析物品质量并保存在gv[]数据中		StringTokenizer tokenizer = new StringTokenizer(goodsVolume, "，, ");		gv = new int[tokenizer.countTokens()+1];//动态的决定数组的长度		while (tokenizer.hasMoreTokens()) {			String d = tokenizer.nextToken();			gv[i] = Integer.valueOf(d);//将字符串转换为整型			i++;		}		//解析物品的价值并保存在gw[]数组中		i = 1;	    tokenizer = new StringTokenizer(goodsWorth, "，, ");	    num = tokenizer.countTokens();		gw = new int[tokenizer.countTokens()+1];		while (tokenizer.hasMoreTokens()) {			String d = tokenizer.nextToken();			gw[i] = Integer.valueOf(d);//将字符串转换为整型			i++;		}		c = Integer.valueOf(backVolume);//得到背包的容量				//为输出测试可以去掉		System.out.println("C ="+ c +";   num ="+ num);		for( i = 1 ;i
    
     =wi     * m[i][j] = m(i+1,j) ;0<=j<=wi;	*/	public void back(int c,int num,int[] gv,int[] gw){//c背包的容量 ， num 背包中物品的个数 ，gv 物品的质量 ，gw物品的价值		int m[][] = new int[num+1][c+1];//定义一个二维数组存放最优值		int i = 0,j = 0,jmax = 0;		int x[] = new int[num+1];//用于存放物品是否放入的标志 1 放入  ， 0 没有放入		jmax = Math.min(gv[num]-1, c);		for( i = 0 ;i <= c ; i++ )//初始化最后一个数据		{			if( i <= jmax ) {				m[num][i] = 0;			}			else{				m[num][i] =gw[num];			}		}		for(i = num -1 ; i > 0 ; i--){			jmax = Math.min(gv[i]-1,c );//当前i物品不能装入的背包容量						for(j = 0; j <= c; j++ ){				if(j <=jmax ){					m[i][j] = m[i+1][j];				}				else {					m[i][j] = Math.max(m[i+1][j], m[i+1][j-gv[i]]+gw[i]);				}			}		}		bestVolume = String.valueOf(m[1][c]);		//输出测试		for(i = 0 ; i <= num ;i++ ){			for(j = 0;j<=c;j++)				System.out.print(m[i][j]+" ");			System.out.println();		}		System.out.println();				//物品的组合方式		for(i = 1 ; i < num; i++ ){			if(m[i][c] == m[i+1][c] )x[i] = 0;			else {				x[i] =1;				c = c - gv[i];			}		}		if(m[num][c]>0)    x[num]=1;		else x[num]=0;		        //结果的赋值		for(i = 1; i <= num ;i++){			System.out.print("x["+i+"]="+x[i]+"  ");			if(i!=num)			group+=x[i] + ", "; 			if(i == num)group+=x[i];			if(x[i]==1){				groupGoodsVolume += gv[i];				groupGoodsWorth  += gw[i];			}					}					}	public String getBestVolume() {				return bestVolume;	}	public String getGroup() {		return group;	}	public String getGroupGoodsVolume() {		return String.valueOf(groupGoodsVolume) ;	}	public String getGroupGoodsWorth() {		return String.valueOf(groupGoodsWorth);	}		}
    

import java.awt.*;import java.awt.event.ActionEvent;import java.awt.event.ActionListener;import javax.swing.BorderFactory;import javax.swing.JButton;import javax.swing.JFrame;import javax.swing.JLabel;import javax.swing.JOptionPane;import javax.swing.JPanel;import javax.swing.JTextField;public class BackProblemJFrame extends JFrame implements ActionListener {	private JLabel backVolumeJL,goodsVolumeJL,goodsWorthJL,bestVolumeJL,groupJL,                    groupGoodsVolumeJL,groupGoodsWorthJL;	private JTextField backVolumeJTF,goodsVolumeJTF,goodsWorthJTF,bestVolumeJTF,groupJTF,	                   groupGoodsVolumeJTF,groupGoodsWorthJTF;	private JPanel jp;	private JButton ok,reset;	BackProblemJFrame (String s){		super(s);		backProblemJFrame();			}		@Override	public void actionPerformed(ActionEvent e) {		// TODO Auto-generated method stub        if(e.getSource()==backVolumeJTF){        	goodsVolumeJTF.requestFocusInWindow();        }        else if(e.getSource()==goodsVolumeJTF){        	goodsWorthJTF.requestFocusInWindow();        }        else if(e.getSource() == reset ){//重置        	backVolumeJTF.setText("");        	goodsVolumeJTF.setText("");        	goodsWorthJTF.setText("");        	bestVolumeJTF.setText("");    		groupJTF.setText("");    		groupGoodsVolumeJTF.setText("");    		groupGoodsWorthJTF.setText("");        }        else if(e.getSource() == goodsWorthJTF||e.getSource() == ok){//确定        	BackProblemArithmetic bpa = new BackProblemArithmetic();        	String bv = backVolumeJTF.getText() ,gv = goodsVolumeJTF.getText(),gw = goodsWorthJTF.getText();        	if(bpa.isNumber(bv,gv,gw)){//如果数字有效        		bpa.backAnswer();        		bestVolumeJTF.setText(bpa.getBestVolume());        		groupJTF.setText(bpa.getGroup());        		groupGoodsVolumeJTF.setText(bpa.getGroupGoodsVolume());        		groupGoodsWorthJTF.setText(bpa.getGroupGoodsWorth());        	}        	else {        		JOptionPane.showMessageDialog(this,"输入的数据必须是数字且" +        				"物品的容量/n物品的价值不能为空！", "警告",        				JOptionPane.WARNING_MESSAGE);        	}        }	}	private void backProblemJFrame() {		// TODO 主界面方法		this.setLayout(null);//设置为空布局  默认的是边界布局		backVolumeJL = new JLabel("请输入背包的容量：");		backVolumeJL.setBounds(30,5,125,25);		this.add(backVolumeJL);				backVolumeJTF = new JTextField(10);		backVolumeJTF.setBounds(160,5,80,25);		backVolumeJTF.addActionListener(this);		this.add(backVolumeJTF);				goodsVolumeJL = new JLabel("请输入所有物品的质量（个数不限，以逗号隔开）");		goodsVolumeJL.setBounds(5,35,300,25);		this.add(goodsVolumeJL);				goodsVolumeJTF = new JTextField(40);		goodsVolumeJTF.setBounds(10,65,270,25);		goodsVolumeJTF.addActionListener(this);	    this.add(goodsVolumeJTF);	    	    goodsWorthJL = new JLabel("请输入物品的价值（以逗号隔开，默认为零）");		goodsWorthJL.setBounds(10,95,300,25);		this.add(goodsWorthJL);				goodsWorthJTF = new JTextField(40);		goodsWorthJTF.setBounds(10,125,270,25);		goodsWorthJTF.addActionListener(this);	    this.add(goodsWorthJTF);	    	    ok = new JButton("确         定");	    ok.setBounds(10,155,120,25);	    ok.addActionListener(this);	    this.add(ok);	    	    reset = new JButton("重           置");	    reset.setBounds(160,155,120,25);	    reset.addActionListener(this);	    this.add(reset);	    	    jp = new JPanel();	    jp.setBorder(BorderFactory.createTitledBorder("结果"));	    jp.setBounds(10,185,270,150);	    jp.setLayout(null);	    this.add(jp);			    bestVolumeJL = new JLabel("最优值：");	    bestVolumeJL.setBounds(10,20,70,25);	    jp.add(bestVolumeJL);	    	    bestVolumeJTF = new JTextField();	    bestVolumeJTF.setBounds(80, 20, 180, 25);	    bestVolumeJTF.setEditable(false);	    jp.add(bestVolumeJTF);	    	    groupJL = new JLabel("组合方式：");	    groupJL.setBounds(10,50,70,25);	    jp.add(groupJL);	    	    groupJTF = new JTextField();	    groupJTF.setBounds(80,50,180,25);	    groupJTF.setEditable(false);	    jp.add(groupJTF);	    	    groupGoodsVolumeJL = new JLabel("物品质量：");	    groupGoodsVolumeJL.setBounds(10,80,70,25);	    jp.add(groupGoodsVolumeJL);	    	    groupGoodsVolumeJTF = new JTextField();	    groupGoodsVolumeJTF.setBounds(80,80,180,25);	    groupGoodsVolumeJTF.setEditable(false);	    jp.add(groupGoodsVolumeJTF);	    	    groupGoodsWorthJL = new JLabel("物品价值：");	    groupGoodsWorthJL.setBounds(10,110,70,25);	    jp.add(groupGoodsWorthJL);	    	    groupGoodsWorthJTF = new JTextField();	    groupGoodsWorthJTF.setBounds(80,110,180,25);	    groupGoodsWorthJTF.setEditable(false);	    jp.add(groupGoodsWorthJTF);	    //界面的设置		Toolkit tk = getToolkit();		Dimension dim = tk.getScreenSize(); 	    this.setResizable(false);		this.setBounds(dim.width/2-150, dim.height/2-200,300,380);		this.setVisible(true);		this.setDefaultCloseOperation(EXIT_ON_CLOSE);	}	}