back_track.java

使用回溯法解决背包问题

package Back_Track;

public class Back_Track {

	/**
	 * @param args
	 */
	private int total_value;	//记录最大价值
	private int total_weight;	//记录价值最大时的重量
	private int temp_value;		//当前价值
	private int temp_weight;	//当前重量
	private int max_weight;		//允许的最大重量
	private int[][] solution;	//记录解空间
	private int[] weight;		//记录物品重量的数组
	private int[] value;		//记录物品价值的数组
	
	
	Back_Track(int[] w,int[] v,int max)		//构造函数
	{
		weight = w;
		value = v;
		max_weight = max;
		solution = new int[8][3];		
		for(int i=0;i<8;i++)				//构造解空间
		{
			solution[i] = new int[3];
			toSolution(solution[i],i);
		}
	}
	
	public void toSolution(int[] s,int val)
	{
		int i=val,j;
		for(int k=0;k<3;k++)
		{
			j = i%2;
			i = i/2;
			s[k] = j;
		}
	}
	
	public void calculate(){
		int i=0;
		int flag;								//flag用于标记是否需要扩展当前节点，为0时不用扩展
		total_value = 0;
		total_weight = 0;
		for(i=0;i<8;i++)
		{
			temp_weight = 0;
			temp_value = 0;
			flag = 1;
			if(solution[i][0]==1)
			{
				temp_weight+=weight[0];
				temp_value+=value[0];
			}
			if(temp_weight>max_weight)
			{
				temp_value = temp_value-value[0];
				temp_weight = temp_weight-weight[0];				
				flag = 0;
				
			}
			if(temp_value>total_value)	
			{
				total_value = temp_value;
				total_weight = temp_weight;
			}
			//System.out.println("current weight:"+temp_weight+" current value:"+temp_value);
			if(solution[i][1]==1&&flag ==1)
			{
				temp_weight+=weight[1];
				temp_value+=value[1];			
			}
			if(temp_weight>max_weight)
			{
				temp_value = temp_value-value[1];
				temp_weight = temp_weight-weight[1];				
				flag = 0;
			}
			if(temp_value>total_value)	
			{
				total_value = temp_value;
				total_weight = temp_weight;
			}
			//System.out.println("current weight:"+temp_weight+" current value:"+temp_value);
			if(solution[i][2]==1&&flag ==1)
			{
				temp_weight+=weight[2];
				temp_value+=value[2];
			}
			if(temp_weight>max_weight)
			{
				temp_value = temp_value-value[2];
				temp_weight = temp_weight-weight[2];						
			}
			if(temp_value>total_value)	
			{
				total_value = temp_value;
				total_weight = temp_weight;
			}		
			//System.out.println("current weight:"+temp_weight+" current value:"+temp_value);
		}
		
		
	}
	
	public void showSolution()
	{
		for(int i=0;i<8;i++)
			for(int j=2;j>=0;j--)
			{
				System.out.print(solution[i][j]+" ");
			}
	}
	
	public void show(){
		System.out.println("max value is:"+total_value+"\nmax weight is:"+total_weight);
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int value[] = {5,4,3};
		int weight[] = {2,3,1};
		int max = 5;
		Back_Track back_track = new Back_Track(weight,value,max);
		back_track.calculate();
		//back_track.showSolution();
		back_track.show();
		
	}

}