knapsack.java

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

 
public class Knapsack {
	public static void knapsack(int []v, int []w, int c, int [][]m)
	{
		int n=v.length-1;
		int jMax=Math.min(w[n]-1,c);
		for (int j=0;j<=jMax;j++)
			m[n][j]=0;
		for (int j=w[n];j<=c;j++)
			m[n][j]=v[n];
		for (int i=n-1;i>1;i--) {
			jMax=Math.min(w[i]-1,c);
			for (int j=w[i];j<=jMax;j++)
			m[i][j]=m[i+1][j];
			for (int j=w[i];j<=c;j++)
				m[i][j]=Math.max(m[i+1][j],m[i+1][j-w[i]]+v[i]);
		}
		m[1][c]=m[2][c];
		if (c>=w[1])
			m[1][c]=Math.max(m[1][c],m[2][c-w[1]]+v[1]);
	}
	
	public static void traceback(int [][]m, int []w, int c,int []x)
	{
		int n=w.length-1;
		for (int i=1;i<n;i++)
			if (m[i][c]==m[i+1][c]) x[i]=0;
			else 
			{ 
				x[i]=1;
				c-=w[i];			
			}
		x[n]=(m[n][c]>0)?1:0;
	}
	
	public static void output(int []w, int []v, int []x)
	{
		System.out.println("Weight\tValue");
		int n=v.length;
		int 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);
		System.out.println("Maximal total value="+totalvalue);
	}
	
	public static void main(String args[])
	{		
		int v[]=new int[]{10,20,30,50,25,60,5 ,20}; /* 初始化背包的价值数组Vi */
		int w[]=new int[]{20, 5,20,15,8 ,35,10,25}; /* 初始化背包的重量数组Wi */
		
		int n= v.length; /* n=v数组的长度 */
				
		int x[]=new int[n]; /* 初始化x数组 */
		
		int c=70; /* 背包最大容量c */
		
		/* 计算背包容量总和sum */
		int sum=0;
		for (int i=0;i<n;i++) sum+=w[i];
		
		int m[][]=new int[n][sum]; /* 初始化二维数组m */
		
		/* 计算在不超过背包容量的情况下能装载的最大价值总和  */
		knapsack(v,w,c,m);
		
		/* 根据m数组的记录，构造最优的一种取法 */
		traceback(m,w,c,x);
		
		/* 输出结果 */
		output(w,v,x);		
	}

}