0-1背包二维数组模板代码

详细解析🔗

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) {
    // 定义dp数组：dp[i][j]表示背包容量为j时，前i个物品能获得的最大价值
    int[][] dp = new int[weight.length][bagsize + 1];
    // 初始化：背包容量为0时，能获得的价值都为0
    for (int i = weight[0]; i <= bagsize; i++) {
        dp[0][i] = value[0];
    }
    // 遍历顺序：先遍历物品，再遍历背包容量(可以交换)
    for (int i = 1; i < weight.length; 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]] + value[i]);
            }
        }
    }
    //打印dp数组
    for (int i = 0; i < weight.length; i++) {
        for (int j = 0; j <= bagsize; j++) {
            System.out.print(dp[i][j] + " ");
        }
        System.out.print("\n");
    }
}

滚动数组的优化版本

注意：一维数组遍历背包只能倒序遍历背包，防止物品多次放入。
倒序就是先算dp[2]
dp[2] = dp[2 - weight[0]] + value[0] = 15 （dp数组已经都初始化为0）
dp[1] = dp[1 - weight[0]] + value[0] = 15
且应该先遍历物品，在遍历背包，因为在二维数组中，通过dp[i][j-1]是由上一层推出，并且不会被覆盖，而一维数组如果从前向后遍历，那么就会被覆盖。

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[] dp = new int[bagsize + 1];
    // 遍历物品
    for (int i = 0; i < weight.length; i++) {
        // 遍历背包
        for (int j = bagsize; j >= weight[i]; j--) {
            dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    for (int i = 0; i < bagsize; i++) {
        System.out.print(dp[i] + " ");
    }
}