二维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<weight[0]，dp[0][j] = 0
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][bagSize + 1];

          for (int j = weight[0]; j <= bagWeight; j++) {
        　　　　dp[0][j] = value[0];
    　　　}

//遍历顺序：先遍历物品，再遍历背包容量
        for (int i = 1; i < wLen; i++){
            for (int j = 0; j <= bagSize; j++){
                if (j < weight[i]){
                    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]);
                }
            }
        }
        //打印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");
        }
    }

优化：

具体实现：

1.确定dp数组的定义

dp[j]：容量为j的背包，所背的物品价值可以最大为dp[j]

2.一维dp数组的递推公式

两个选择：

（1）保持自己，dp[j]相当于二维dp数组中的dp[i-1][j]，即不放物品i

（2）dp[j - weight[i]] + value[i]，把不合适的东西掏出来让背包变成刚好缺物品i重量的背包，放物品i

3.初始化

dp数组内元素都初始化为0

4.遍历顺序

倒序遍历：保证物品i只被放入一次

如果是正序的话：

dp[1] = dp[1 - weight[0]] + value[0] = 15

dp[2] = dp[2 - weight[0]] + value[0] = 30

物品0被放入两次

如果是倒序的话：

dp[2] = dp[2 - weight[0]] + value[0] = 15 （dp数组已经都初始化为0）

dp[1] = dp[1 - weight[0]] + value[0] = 15

5.举例

代码：

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

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

完全背包

完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。问背包能背的物品最大价值是多少？

01背包和完全背包唯一不同就是体现在遍历顺序上

01背包核心代码

for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
}

01背包内嵌的循环是从大到小遍历，为了保证每个物品仅被添加一次。

而完全背包的物品是可以添加多次的，所以要从小到大去遍历

// 先遍历物品，再遍历背包
for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = weight[i]; j < bagWeight ; j++) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

    }
}

举例：

//先遍历物品，再遍历背包
    private static void testCompletePack(){
        int[] weight = {1, 3, 4};
        int[] value = {15, 20, 30};
        int bagWeight = 4;
        int[] dp = new int[bagWeight + 1];
        for (int i = 0; i < weight.length; i++){
            for (int j = 1; j <= bagWeight; j++){
                if (j - weight[i] >= 0){
                    dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
                }
            }
        }
        for (int maxValue : dp){
            System.out.println(maxValue + "   ");
        }
    }

    //先遍历背包，再遍历物品
    private static void testCompletePackAnotherWay(){
        int[] weight = {1, 3, 4};
        int[] value = {15, 20, 30};
        int bagWeight = 4;
        int[] dp = new int[bagWeight + 1];
        for (int i = 1; i <= bagWeight; i++){
            for (int j = 0; j < weight.length; j++){
                if (i - weight[j] >= 0){
                    dp[i] = Math.max(dp[i], dp[i - weight[j]] + value[j]);
                }
            }
        }
        for (int maxValue : dp){
            System.out.println(maxValue + "   ");
        }
    }