01背包的问题是,现在有一个容量为capacity的背包和n个物品。每个物品有且仅有一件,并且每个物品的体积volume和价值value均已知。现在需要知道在不超过背包的容量的情况下，可以装下的物品的总价值的最大值。

本问题可以用动态规划来做，需要一个二维数组matrix来保存状态和状态转移得到新的状态，此处的状态即为在给定的前i(0<=i<=n)件物品和j(0<=j<=capacity)容量下，可以得到的价值最大值。

数组有0～n共计n+1行，表示从第0个物品（也即没有可选物品）扫描到第n个物品；数组有0～capacity共计capacity+1列，表示假如背包的容量为0、1、2...capacity的情况。注意这里多了一行和一列，即第0行(matrix[0][0~capacity])和第0列(matrix[0~n][0])。他们的值都为0，原因也很简单：第0行代表没有物品可选，不管背包的容量是0还是capacity，最大价值都为0；同样地，第0列代表背包容量为0的情况，不管有多少件可选的物品，一件都装不下，最大价值依然为0。

将二维数组的第0行和第0列都初始化0。我们将从第1行开始，一行行从左往右填写dp table。填写规则是，当我们在填写第i行时（也即考虑到第i件物品时），在第j列（也就是考虑假如当前背包容量只有j时），考虑两种情况：第一种情况是当前的第i件物品的体积volume[i]直接就超过了当前的背包容量j，所以当前物品不可能被放入背包，所以当前状态的价值最大值和只有前i-1件物品在相同的背包容量j下的最大价值相同（相当于有没有第i件物品没差），所以直接将上一个单元格的值复制下来，即matrix[i][j]=matrix[i-1][j]第二种情况是，当前的第i件物品的体积volume[i]<=当前的背包容量j，也就是说，这件物品是可以被放入背包的。究竟放不放呢？需要比较是放能达到的最大总价值大还是不放能达到的最大总价值大。假如放，则当前第i件物品会占据volume[i]的体积，则背包还剩下j-volume[i]的体积，那么剩下的j-volume[i]体积最多可以放多少价值的东西呢，我们可以查找第j-volume[i]列，这一列不正好对应了在背包容积只有j-volume[i]时价值最大的方案吗，由于第i件物品只能被放入一次，既然当前已经放在了volume[i]的体积里，所以在剩下的j-volume[i]的体积里必然只能放前i-1件物品了，也就是单元格matrix[i-1][j-volume[i]]对应的值；假如不放，那也就相当于不考虑第i件物品，和第i件物品超出容量的效果是一样的，照搬上一个单元格的值matrix[i-1][j]。现在就需要比较这在=两种方案谁的值比较大，也就是matrix[i][j]=Math.max(value[i]+matrix[i-1][j-volume[i]],matrix[i-1][j])。

当我们遍历到第n行第capacity列时，整个dp table填写完毕，右下角的matrix[n][capacity]的值就是我们要找的最大价值。代码如下：

/**
* 
* @param capacity 背包容量
* @param n 物品件数
* @param value 表示物品价值的数组，value[i]表示第i件物品的价值，为了方便，数组长度为n+1，1<=i<=n
* @param volume 表示物品体积的数组，volume[i]表示第i件物品的体积，为了方便，数组长度为n+1，1<=i<=n
* @return 返回可以装下的最大物品价值
*/
public static int maxValue(int capacity,int n, int[] value,int[] volume){
    int[][] matrix =new int[n+1][capacity+1];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= capacity; j++) {
            //在j个容量下  放不下当前第i个物品
            if(volume[i]>j){
                matrix[i][j]=matrix[i-1][j];
            //在j个容量下  放得下当前第i个物品
            }else{
                //比较两个值哪个大:
                //要么选取当前第i件放入背包,加上在i-1件物品在j-volume[i]空间里的最大价值方案
                //要么维持之前i-1件物品的方案维持不变
                matrix[i][j]=Math.max(value[i]+matrix[i-1][j-volume[i]],matrix[i-1][j]);
            }
        }
    }
    return matrix[n][capacity];
    }