背包最大重量为4，物品如下，问背包能背的物品最大价值是多少？

 二维dp数组01背包

1.确定dp数组以及下标的含义

dp[i][j]表示从下标为[0-i]的物品中任意取，放进容量为j的背包，价值总和最大为多少

2.确定递推公式

两个方向推导

• 不放物品i：dp[i][j]=dp[i-1][j]
• 放物品：dp[i][j]=dp[i-1][j-weight[i]] + value[i]

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

3.dp数组初始化

如果背包容量j是0的话，dp[i][0]，无论选取哪些物品，背包价值总和一定为0

 dp[0][j]，i为0，存放编号0的物品时，各个容量的背包能存放的最大价值

• j
• j>=weight[0] ,  dp[0][j] = value[0]

 4.确定遍历顺序

从左到右，从上到下

5.举例推导

 代码：

public static void main(String[] args) {
        int[] weight = {1, 3, 4};
        int[] value = {15, 20, 30};
        int bagSize = 4;
        testWeightBagProblem(weight, value, bagSize);
    }

    public static void testWeightBagProblem(int[] weight, int[] value, int bagSize){
        int wLen = weight.length, value0 = 0;
        //定义dp数组：dp[i][j]表示背包容量为j时，前i个物品能获得的最大价值
        int[][] dp = new int[wLen + 1][bagSize + 1];
        //初始化：背包容量为0时，能获得的价值都为0
        for (int i = 0; i <= wLen; i++){
            dp[i][0] = value0;
        }
        //遍历顺序：先遍历物品，再遍历背包容量
        for (int i = 1; i <= wLen; i++){
            for (int j = 1; j <= bagSize; j++){
                if (j < weight[i - 1]){
                    dp[i][j] = dp[i - 1][j];
                }else{
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + value[i - 1]);
                }
            }
        }
        //打印dp数组
        for (int i = 0; i <= wLen; i++){
            for (int j = 0; j <= bagSize; j++){
                System.out.print(dp[i][j] + " ");
            }
            System.out.print("\n");
        }
    }