回溯法求解01背包问题

1.1 算法设计思想

用回溯法解决01背包问题，这实际是一个子集树问题：

首先对于背包中的物品按照单位重量价值进行排序，方便于后面子树的剪枝操作。

对于背包中的每一个物品，可以选择放入（左子树）或者不放入（右子树）。依次对每个节点进行搜索，得到最优解。

剪枝函数：对于左子树，如果放入物品的重量已经超出背包的容量，则直接进行剪枝。对于右子树，其判断取决于当前背包剩余的容量，依次取背包中剩余的物品中单位重量价值最大的物品（跳过本层物品），最终能否超过此前找到的最优解，如果能够超过，则可以向右搜索，不能超过，则右节点变为死节点。

对于寻找剩余物品的最高价值上界，按照背包中剩余空间依次取剩下的物品，当空间不足以取下一个物品时，则将下一个物品的单位重量价值折算到现在的剩余空间中去计算理想最高上界。

1.2 程序源码
 

import java.util.Scanner;

 

public class Bag {

	static int n;   //n个物品

    static int c;   //背包容量

    static int []weight; //物品重量

    static int[] value; //物品价值

	int maxValue = 0;

	int tempValue;

	int tempWeight;

	int[] way = new int[n]; 

	int[] bestWay = new int[n];

	

 

	public void BackTrack(int t){

		//已经搜索到根节点

		if(t>n-1){

			if(tempValue > maxValue){

				maxValue = tempValue;

				for(int i=0;i<n;i++)

					bestWay[i] = way[i];

			}

			return;

		}

		//搜索左边节点

		if(tempWeight + weight[t] <= c){

			tempWeight += weight[t];

			tempValue += value[t];

			way[t] = 1;

			BackTrack(t+1);

			tempWeight -= weight[t];

			tempValue -= value[t];

			way[t] = 0;

		}

		//不装入这个物品，直接搜索右边的节点

		if( Bound(t+1) >= maxValue){

			BackTrack(t+1);

		}

	}

	//用于计算剩余物品的最高价值上界

	public double Bound(int k){

		double maxLeft = tempValue;

		int leftWeight = c - tempWeight;

		//尽力依照单位重量价值次序装剩余的物品

		while(k <= n-1 && leftWeight > weight[k] ){

			leftWeight -= weight[k];

			maxLeft += value[k];

			k++;

		}

		//不能装时，用下一个物品的单位重量价值折算到剩余空间。

		if( k <= n-1){

			maxLeft += value[k]/weight[k]*leftWeight;

		}

		return maxLeft;

	}

	public static void main(String[] args){

		System.out.println(\"实验六  回溯\");

    		Scanner sc=new Scanner(System.in);

		System.out.print(\"请输入物品数n: \");

		n=sc.nextInt();

		System.out.print(\"请输入背包容量c: \");

		c=sc.nextInt();

		Scanner s=new Scanner(System.in);

		System.out.print(\"请分别输入物品重量weight: \");

		String str=s.nextLine();

		String[] Arrays=str.split(\" \");

		 weight=new int[Arrays.length];

         for(int j=0;j<Arrays.length;j++){

         	weight[j]=Integer.parseInt(Arrays[j]);

         } 

         System.out.print(\"请分别输入物品价值value: \");

         str=s.nextLine();//读入p的行

         String[] Array=str.split(\" \");

         value=new int[Array.length];

         for(int j=0;j<Array.length;j++){

         	value[j]=Integer.parseInt(Array[j]);

         }

		Bag b = new Bag();

		b.BackTrack(0);

		System.out.println(\"该背包能够取到的最大价值为:\"+b.maxValue);

		System.out.println(\"取出的方法为:\");

		for(int i : b.bestWay)

			System.out.print(i+\"  \");

	}

}

1.3 实验结论（结果验证）