mybagframe.java

这是一个0/1背包问题的解决

import java.awt.*;
import javax.swing.*;
import java.awt.event.*;
class Class1{
	int N=50;
	public int limitW,totalV;
	int maxV=9;
	public	String mystring1="";
	public int option[] = new int[N];
	public int cop[]=new int[N];
	
	int weight=1;
	int value=0;
	public int item[][]=new int[N][2];
	
	public int num;
	public void qinkong(){
		for(int i=0;i<N;i++){
			item[i][0]=0;
			item[i][1]=0;
			
		}
		
		maxV=0;
	}
	
	public void find(int i,int tw,int tv)    
	{
		int k;
		if(tw+item[i][weight]<=limitW)
		{	
			cop[i]=1;
			if(i<num-1)find(i+1,tw+item[i][weight],tv);
			else
			{	
				for(k=0;k<num;k++)
					option[k]=cop[k];
				maxV=tv;
		
			}
			cop[i]=0;
		}
			mystring1=String.valueOf(maxV);
		if(tv-item[i][value]>maxV)
			if(i<num-1)find(i+1,tw,tv-item[i][value]);
			else
			{
				for(k=0;k<num;k++)
					option[k]=cop[k];
				maxV=tv-item[i][value];
			
			}
			
	}	
}
class mybagframe implements ActionListener{
	JFrame f=null;
	JLabel label1=null;
	JLabel label2=null;
	JLabel label3=null;
	JLabel label4=null;
	JLabel label5=null;
	JLabel label6=null;
	Class1 class1=new Class1();
	public mybagframe(){
		f=new JFrame("背包问题");
		f.setSize(700,600);
		f.setLocation(100,50);
		Container contentPane=f.getContentPane();
		JPanel panel1=new JPanel();
		JPanel panel2=new JPanel();
		//panel.setLayout(new GridLayout(1,1));
		panel2.setLayout(new GridLayout(5,1));
		JButton b=new JButton("背包问题,CLIKME");
		b.addActionListener(this);
		panel1.add(b);
		label1=new JLabel("",JLabel.CENTER);
		label2=new JLabel("",JLabel.CENTER);
		label3=new JLabel("",JLabel.CENTER);
		label4=new JLabel("",JLabel.CENTER);
		label5=new JLabel("",JLabel.CENTER);
		label6=new JLabel("",JLabel.CENTER);
		panel2.add(label2);
		panel2.add(label3);
		panel2.add(label4);
		panel2.add(label5);
		panel2.add(label6);		
		label1.setText("作者韩小飞于06年9月编");
		contentPane.add(panel1,BorderLayout.NORTH);
		contentPane.add(label1,BorderLayout.SOUTH);
		contentPane.add(panel2,BorderLayout.CENTER);
		f.setVisible(true);
		f.addWindowListener(new WindowAdapter(){
			public void windowClosing(WindowEvent e){
				System.exit(0);
			}
		});
	}
	public void actionPerformed(ActionEvent e){
		label2.setText("");
		label3.setText("");
		label4.setText("");
		label5.setText("");
		class1.qinkong();
		//label1.setText("");
		//label1.setText("");
		String title="Input Dialog";
		String message1="输入物品的总数:";
		String message2="输入背包的重量限制:";
		
		int messageType=JOptionPane.QUESTION_MESSAGE;
		String[] values={"1","2","3"};
		String result1="";
		String result2="";
		result1=JOptionPane.showInputDialog(f,message1,title,messageType);
		result2=JOptionPane.showInputDialog(f,message2,title,messageType);	
		int num=Integer.parseInt(result1, 10);
		class1.limitW=Integer.parseInt(result2, 10);
		class1.num=num;
		String [] resultv=new String [num];
		String [] resultw=new String [num];
		String [] messagev=new String [num];
		String [] messagew=new String [num];
		int total=0;
		for(int i=0;i<num;i++){
			messagev[i]=new String("请输入第"+(i+1)+"个物品的价值:");
			messagew[i]=new String("请输入第"+(i+1)+"个物品的重量:");
			resultv[i]=JOptionPane.showInputDialog(f,messagev[i],title,messageType);
			resultw[i]=JOptionPane.showInputDialog(f,messagew[i],title,messageType);
			
		  	class1.item[i][0]=Integer.parseInt(resultv[i], 10);
			class1.item[i][1]=Integer.parseInt(resultw[i], 10);
			total=total+class1.item[i][0];
		}
		class1.find(0,0,total);
		label2.setText("物品的总数为："+String.valueOf(num));
		label3.setText("背包的重量限制为："+result2);
		String astring="";
		String bstring="";
		for(int i=0;i<num;i++){
			astring=astring+"第"+String.valueOf(i+1)+"件物品价值为"+resultv[i]+",重量为"+resultw[i]+"   ";
			if(class1.option[i]!=0){
				bstring+="物品"+String.valueOf(i+1)+"   ";
			}
			
		}
		label3.setText(astring);
		
		label4.setText("选中的物品为："+bstring);
		label5.setText("背包最多可容纳的物品价值为："+String.valueOf(class1.maxV));
	}
	public static void main(String args[]){
		new mybagframe();	
		
		
	}
}