DP0/1背包问题

/**
*
* @author Administrator
* @version 2011.06.15
* 动态规划法解决0/1背包问题
*/
public class DPBeibao01 {

/**
* @param args
*/
public static void main(String[] args) {
int w[]={0,2,2,6,5,4};
int v[]={0,6,3,5,4,6};
System.out.println(maxValue(w,v,10));

}
/**
*
* @param w存放物品的重量
* @param v存放物品的价值
* @param c背包的容量
* @return
*/
   private static int maxValue(int w[],int v[],int c){
   int len=w.length;
   //val[i][j]表示把前i个物品放入容量为j的背包中得到的价值
   int val[][]= new int[len][c+1];
  
   for(int i=0;i<len;i++){
   val[i][0]=0;
   }
   for(int j=0;j<=c;j++){
   val[0][j]=0;
   }
   for(int i=1;i<len;i++){
   for(int j=1;j<=c;j++){
   if(w[i]>j)val[i][j]=val[i-1][j];
   else{
   val[i][j]=Math.max(val[i-1][j], val[i-1][j-w[i]]+v[i]);    }
   }
   }
   int j=c;
   int z[]=new int[len];//记录物品是否被装入背包中
   for(int m=len-1;m>0;m--){
   if(val[m][j]==val[m-1][j])z[m]=0;
   else{
   z[m]=1;
   j=j-v[m];
   }
   }
   return val[len-1][c];
   }
}