0-1背包问题（Java）

文章参考博文：http://blog.csdn.net/mu399/article/details/7722810。从该文章中熟悉了算法的动态规划思想，简单地用Java实现了算法的思想。

参数：v表示物品的价值，s表示物品的质量，C表示背包的容量。令M[i,j]表示将物品1-i装入容量为j的背包可获得的最大价值（并不是把1-i都放进去），递归式如下：

M(i , j) = Max{ M( i-1, j ) , M( i-1, j-si ) + vi }

Java的实现记录如下：

void ZeroOnePackage(int []v, int[] s, int C){
  int[][] M = new int[v.length][C+1];
  int max = 0;
  for (int i=0; i<v.length; i++){
   if(s[i]<=C)
    for(int j=s[i];j<=C;j++)
     M[i][j] = v[i];
  }
  for (int i=0; i<v.length; i++){
   for(int j=0; j<=C; j++){
    if(i>0 && j-s[i]>=0)
     M[i][j] = Math.max(M[i-1][j],M[i-1][j-s[i]]+v[i] );
    if(M[i][j]>max)
     max = M[i][j];
   }
  }
  System.out.println("Max ="+ max);
 }