알고리즘 자바 실현 - 동적 계획 - 0 - 1 가방 문제

/**
 * 01     （    ）
 * @author Lican
 *
 */
public class Pack01 {
	public int[] v;//    
	public int[] w;//    
	public int c;//    
	public int[][] m;//m(i,j)      j，     ，i，i+1，i+2，i+3,...,n  0-1        
	public int[] x;//   i         ，1：  ；0：   
	public Pack01(int[] vv,int[] ww,int cc){
		this.v=vv;
		this.w=ww;
		this.c=cc;
		this.x=new int[vv.length];
		int max = maxM(w,c);//  j    ，    new     m  ，                
		m = new int[v.length][max+1];
	}
	/**
	 *              ，   m         
	 * @param w
	 * @param c
	 * @return
	 */
	public int maxM(int[] w,int c){
		int max = c;
		for(int i=1;i<w.length;i++){
			if(w[i]>c)
				max=w[i];
		}
		return max;
	}
	public 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=0;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])//  i=1      
			m[1][c]=Math.max(m[2][c], m[2][c-w[1]]+v[1]);
		else
			m[1][c]=m[2][c];
		
	}
	public 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])// i     
				x[i]=0;
			else{
				x[i]=1;
				c-=w[i];//c     
			}
		}
		x[n]=(m[n][c]>0)?1:0;
	}
	public static void main(String[] args) {
		int v[]={0,2,1,4,3};
		int w[]={0,1,4,2,3};
		int c=8;
		Pack01 pa = new Pack01(v,w,c);
		pa.knapsack(pa.v, pa.w, pa.c, pa.m);
		System.out.println("             ：");
		System.out.println(pa.m[1][c]);
		pa.traceback(pa.m, pa.w, pa.c, pa.x);
		System.out.println("         ：");
		for(int i=0;i<=v.length-1;i++){
			if(pa.x[i]==1)
				System.out.print(i+" ");
		}
	}
}