0-1背包问题（动态规划法-DP含一维滚动数组优化）

0-1背包问题：
有n个重量分别为{w1，w2，…，wn}的物品，它们的价值分别为{v1，v2，…，vn}，给定一个容量为W的背包。小偷要选择从这些物品中偷一部分物品放入该背包的方案，每个物品要么偷要么不偷，要求选中的物品不仅能够放到背包中，而且重量和为W具有最大的价值。

动态规划法采用递归实现，时间复杂度是0(nC) ：

经典公式的推导.png

Java代码实现如下：

public class Main {

    public static void main(String[] args) {
        KnapSack knapSack = new KnapSack();
        int b[][] = knapSack.call();
        System.out.println(b[5][20]);

    }
}


class KnapSack{
    private static final int N = 6;//商品种类。包含第0个这个特殊值
    private static final int C = 21;//总可用容量
    private static final int w[]={0,2,3,4,5,9};  //每个商品容量
    private static final int v[]={0,3,4,5,8,10}; //每个商品价值

    public int[][] call(){
        //计算用
        int B[][] = new int[N][C];
        for(int n=1;n<N;n++){
            for(int c=1;c<C;c++){
                if(w[n] > c){
                    //无法偷
                    B[n][c] = B[n-1][c];
                }else{
                    //偷
                    int yesN = B[n-1][c-w[n]]+v[n];
                    //不偷
                    int noN = B[n-1][c];
                    B[n][c] = Math.max(yesN,noN);
                }
            }

        }
        return B;
    }

    //优化：由于B[i][j]是从前一个状态B[i-1][j]得到的，
    // 只与前一个状态有关，那么即可优化为一维滚动数组B[]，
    public int[] call2(){
        //计算用
        int B[] = new int[C];
        for(int n=1;n<N;n++){
            for(int c=C-1;c>=w[n];c--){
                int yesN = B[c-w[n]]+v[n];
                int noN = B[c];
                B[c] = Math.max(yesN,noN);
            }
        }
        return B;
    }

}