编辑代码

import java.util.Arrays;

public class Knapsack {

    public static void main(String[] args) {
        // 物品的重量
        int[] weights = {2, 3, 4, 5};

        // 物品的价值
        int[] values = {3, 4, 5, 6};

        // 背包的容量
        int capacity = 5;

        // 使用分支界限法求解背包问题
        int maxValue = knapsack(weights, values, capacity);

        // 打印背包的最大价值
        System.out.println("背包的最大价值：" + maxValue);
    }

    private static int knapsack(int[] weights, int[] values, int capacity) {
        // 如果背包的容量为 0，则背包的最大价值为 0
        if (capacity == 0) {
            return 0;
        }

        // 如果物品的数量为 0，则背包的最大价值为 0
        if (weights.length == 0) {
            return 0;
        }

        // 创建一个二维数组来存储子背包的最大价值
        int[][] dp = new int[weights.length + 1][capacity + 1];

        // 初始化二维数组的第一行和第一列
        for (int i = 0; i <= weights.length; i++) {
            dp[i][0] = 0;
        }
        for (int j = 0; j <= capacity; j++) {
            dp[0][j] = 0;
        }

        // 计算每个子背包的最大价值
        for (int i = 1; i <= weights.length; i++) {
            for (int j = 1; j <= capacity; j++) {
                // 如果当前物品的重量大于背包的容量，则当前物品不能放入背包
                if (weights[i - 1] > j) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    // 如果当前物品的重量小于或等于背包的容量，则当前物品可以放入背包
                    dp[i][j] = Math.max(dp[i - 1][j], values[i - 1] + dp[i - 1][j - weights[i - 1]]);
                }
            }
        }

        // 返回背包的最大价值
        return dp[weights.length][capacity];
    }
}