回溯法——01背包问题

问题不多描述

直接说思路:构造解空间树。在搜索解空间树时，只要左子节点是一个可行结点，就进入其左子树。对于右子树时，先计算上界函数，以判断是否将其减去。

代码如下:(Java实现)

import java.util.Scanner;

public class Knapsack {
	static int W;//箱子容量
	static int n;//物品数量
	static int []w;//物品重量
	static int []v;//物品价值
	static int maxValue;//最大的价值
	static int []x;//最佳路径
	static int []cx;//中间路径
	static int cw;//中间所取物品重量总和
	static int cv;//中间所去物品价值总和
	static void dfs(int k){
		if(k>=n){//出口
			if(cv>maxValue){
				maxValue=cv;
				for(int i=0;i<n;i++){
					x[i]=cx[i];
				}
			}
			return;
		}
	 if(cw+w[k]<=W){
			cx[k]=1;
			cw+=w[k];
			cv+=v[k];
			dfs(k+1);
			cw-=w[k];//回溯
			cv-=v[k];
		}
		cx[k]=0;
		dfs(k+1);
	}
	public static void main(String[] args) {
		Scanner input=new Scanner(System.in);
		System.out.println("箱子容量:");
		W=input.nextInt();
		System.out.println("物品数量:");
		n=input.nextInt();
		w=new int[n];
		v=new int[n];
		x=new int[n];
		cx=new int[n];
		System.out.println("每一件物品的重量:");
		for(int i=0;i<n;i++){
			w[i]=input.nextInt();
		}
		System.out.println("每一件物品的价值:");
		for(int i=0;i<n;i++){
			v[i]=input.nextInt();
		}
		dfs(0);
		System.out.println("最大价值:"+maxValue);
		System.out.println("所取物品:");
		for(int i=0;i<x.length;i++){
			System.out.print(x[i]+" ");
		}
	}
}