Knapsack Problem in java（背包问题）

CompleteKnapsack.java

// 完全背包问题
public class Main {
    public static void main(String[] args) {
        int[] weight = {1, 3, 4};
        int[] value = {15, 20, 30};
        int bagSize = 4;
        test2DimWeightBagProblem(weight, value, bagSize);
        test1DimWeightBagProblem(weight, value, bagSize);
    }

    public static void test2DimWeightBagProblem(int[] weight, int[] value, int bagSize) {
        int wlen = weight.length;
        //定义dp数组：dp[i][j]表示背包容量为j时，前i个物品能获得的最大价值
        int[][] dp = new int[wlen][bagSize + 1];

        // 初始化：根据递推公式，需要初始化dp[0][j]，注意从weight[0]开始
        for (int i = weight[0]; i < bagSize+1; i++) {
            // 初始化较0-1背包有变化，具体情况具体分析
            dp[0][i] = dp[0][i - weight[0]] + value[0];
        }
        // 初始化：背包容量为0时，能获得的价值都为0
        for (int i = 0; i < wlen; i++) {
            dp[i][0] = 0;
        }

        // 遍历顺序：先遍历物品，再遍历背包容量
        for (int i = 1; i < wlen; i++) {
            for (int j = 1; j < bagSize+1; j++) {
                if (j < weight[i]) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                // 此处转移公式改为由 dp[i][j - weight[i]]转移
                // 这是因为 dp[i][j - weight[i]]时是最大限度放i件物品，如果在放的话，只能放一件了
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - weight[i]] + value[i]);
                }
            }
        }
        //打印dp数组
        System.out.println("2Dim: ");
        for (int i = 0; i < wlen; i++) {
            for (int j = 0; j < bagSize+1; j++) {
                System.out.print(dp[i][j] + " ");
            }
            System.out.print("\n");
        }
    }

    public static void test1DimWeightBagProblem(int[] weight, int[] value, int bagSize) {
        int wlen = weight.length;

        //定义dp数组：dp[j]表示背包容量为j时，能获得的最大价值
        int[] dp = new int[bagSize + 1];

        // 具体的遍历顺序和递增递减视情况而定
        for (int i = 0; i < wlen; i++) {
            for (int j = weight[i]; j <= bagSize; j++) {
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
            }
        }

        //打印dp数组
        System.out.println("1Dim: ");
        for (int j = 0; j <= bagSize; j++){
            System.out.print(dp[j] + " ");
        }

    }
}

Knapsack01.java

// 0-1背包问题
public class Main {
    public static void main(String[] args) {
        int[] weight = {1, 3, 4};
        int[] value = {15, 20, 30};
        int bagSize = 4;
        test2DimWeightBagProblem(weight, value, bagSize);
        test1DimWeightBagProblem(weight, value, bagSize);
    }

    public static void test2DimWeightBagProblem(int[] weight, int[] value, int bagSize) {
        int wlen = weight.length;
        //定义dp数组：dp[i][j]表示背包容量为j时，前i个物品能获得的最大价值
        int[][] dp = new int[wlen][bagSize + 1];

        // 初始化：根据递推公式，需要初始化dp[0][j]，注意从weight[0]开始
        for (int i = weight[0]; i < bagSize+1; i++) {
            dp[0][i] = value[0];
        }
        // 初始化：背包容量为0时，能获得的价值都为0
        for (int i = 0; i < wlen; i++) {
            dp[i][0] = 0;
        }

        // 遍历顺序：先遍历物品，再遍历背包容量
        for (int i = 1; i < wlen; i++) {
            for (int j = 1; j < bagSize+1; j++) {
                if (j < weight[i]) {
                // 不放物品i
                    dp[i][j] = dp[i - 1][j];
                } else {
                // 放物品i
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
                }
            }
        }
        //打印dp数组
        System.out.println("2Dim: ");
        for (int i = 0; i < wlen; i++) {
            for (int j = 0; j < bagSize+1; j++) {
                System.out.print(dp[i][j] + " ");
            }
            System.out.print("\n");
        }
    }

    public static void test1DimWeightBagProblem(int[] weight, int[] value, int bagSize) {
        int wlen = weight.length;

        //定义dp数组：dp[j]表示背包容量为j时，能获得的最大价值
        int[] dp = new int[bagSize + 1];

        //遍历顺序：先遍历物品，再遍历背包容量
        for (int i = 0; i < wlen; i++) {
            // 因为滚动数组的原因
            // 背包容量遍历必须从大到小
            for (int j = bagSize; j >= weight[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
            }
        }

        //打印dp数组
        System.out.println("1Dim: ");
        for (int j = 0; j <= bagSize; j++){
            System.out.print(dp[j] + " ");
        }
        
    }
}