01背包问题----动态规划

package zju;

public class PackageTest {
    /*  
     *  题目：给定n个物体，其中第i个物体重量wi，价值vi ，另有一个最大载重m的背包，往里面塞东西使得总价值尽可能大   
     *  令f(i,j)表示用前i个物体装出重量为j的组合时的最大价值
     *  f(i,j)=max{f(i-1,j), f(i-1, j-w[i])+v[i] } ,i>0, j>=w[i];
     *  f(i,j) = f(i-1,j) , i>0, j<w[i];
     *  f(0,j) = v[0] , i=0, j>=w[0];    
     *  f(0,j) = 0, i=0, j<w[0];
     */
	
	public int countValues(int m,int w[],int v[]){	
		int[][] c=new int[w.length][m+1];
		//初始化数组c前一排
		for(int k=0;k<=m;k++){
			if(k>=w[0]){
				c[0][k]=v[0];
			}else{
				c[0][k]=0;
				
			}
		}
		
		//计算总价值
		for(int i=1;i<w.length;i++){	
			for(int j=0;j<=m;j++){
				if(j<w[i]){
					c[i][j]=c[i-1][j];
					
				}else if(c[i-1][j]>=c[i-1][j-w[i]]+v[i]){
					c[i][j]=c[i-1][j];
				}else{
					c[i][j]=c[i-1][j-w[i]]+v[i];
				}
			}
		}
		//打印数组c,可省略
		for(int i=0;i<w.length;i++ ){
			for(int j=0;j<=m;j++){
				System.out.print(c[i][j]+"  ");
			}
			System.out.println();
		}
		return c[w.length-1][m];
	}
	
	public static void main(String[] args) {
		
		int w[] = {2,2,6,5,4};    
        int v[] = {6,3,7,4,6};    
        int m=10;
        
        PackageTest p=new PackageTest();
        System.out.println("The most value is:"+p.countValues(m, w, v));
	}

}