knapsack2.java

《算法设计与分析》王晓东编著

public class Knapsack2 {
	public static double knapsack(double []w, double []v,double c,
			                      double [][]p,int []head)
	{		
		int n=v.length-1;
		head[n+1]=0;
		p[0][0]=0;
		p[0][1]=0;
		int left=0, right=0, next=1;
		head[n]=1;
		for (int i=n;i>=1;i--) {
			int k=left;
			for (int j=left;j<=right;j++) {
				if (p[j][0]+w[i]>c) break;
				double y=p[j][0]+w[i],
				       m=p[j][1]+v[i]; /* p[j][0]表示负重之和，p[j][1]表示价值之和 */
				
				while (k<=right && p[k][0]<y) {
					p[next][0]=p[k][0];
					p[next++][1]=p[k++][1];					
				}
				if (k<=right && p[k][0]==y) {
					if (m<p[k][1]) m=p[k][1];
					k++;
				}
				
				if (m>p[next-1][1]) {
					p[next][0]=y;
					p[next++][1]=m;
				}
				while (k<=right && p[k][1]<=p[next-1][1]) k++;				
			}
			while (k<=right) {
				p[next][0]=p[k][0];
				p[next++][1]=p[k++][1];
			}
			left=right+1;
			right=next-1;
			head[i-1]=next;
		}
		return p[next-1][1];
	}
	
	public static void traceback(double []w,double []v,double [][]p,
			                     int []head, int []x)
	{
		int n=w.length-1;
		double j=p[head[0]-1][0],m=p[head[0]-1][1];
		for (int i=1;i<=n;i++) {
			x[i]=0;
			for (int k=head[i+1];k<=head[i]-1;k++) {
				if (p[k][0]+w[i]==j && p[k][1]+v[i]==m) {
					x[i]=1;
					j=p[k][0];
					m=p[k][1];
					break;
				}				
			}				
		}
	}
	
	public static void output(double []w, double []v, int []x)
	{
		System.out.println("Weight\tValue");
		int n=v.length;
		double totalweight=0,totalvalue=0;
		for (int i=0;i<n;i++)
			if (x[i]>0){
				totalweight+=w[i];
				totalvalue+=v[i];
				System.out.println(w[i]+"\t"+v[i]);
			}
		System.out.println("Total weight="+totalweight);		
	}

	public static void main(String[] args) {
		double v[]=new double[]{10,20,30,50,25,60,5 ,20}; /* 初始化背包的价值数组Vi */
		double w[]=new double[]{20,5,20,15,8,35,10,25}; /* 初始化背包的重量数组Wi */
		
		int n= v.length; /* n=v数组的长度 */
				
		int x[]=new int[n]; /* 初始化x数组 */
		
		double c=70; /* 背包最大容量c */
		
		double p[][]=new double[n*n][2]; /* 初始化二维数组p */
		
		int head[]=new int[n+1]; /* heap[i]表示第i遍更新时，添加进数组p的“头位置” */		
		
		/* 计算在不超过背包容量的情况下能装载的最大价值总和  */
		System.out.println("Maximal total value="+knapsack(w,v,c,p,head)+"\n");
		
		/* 根据m数组的记录，构造最优的一种取法 */
		traceback(w,v,p,head,x);
		
		/* 输出结果 */
		output(w,v,x);
	}
}