0/1背包问题 java代码

0/1背包问题是一个经典的动态规划问题，假设有n个物品，每个物品有自己的重量和价值，在限定的总重量内选取若干个物品，使它们的总重量不超过限定值，且总价值最大。以下是Java代码实现：

public class ZeroOneKnapsack {
    public static void main(String[] args) {
        int[] weights = {2, 3, 4, 5}; // 物品的重量
        int[] values = {3, 4, 5, 6}; // 物品的价值
        int maxWeight = 8; // 背包的最大承重
        int maxValue = knapsack(weights, values, maxWeight);
        System.out.println("背包最大价值为：" + maxValue);
    }

    private static int knapsack(int[] weights, int[] values, int maxWeight) {
        int n = weights.length;
        int[][] dp = new int[n + 1][maxWeight + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= maxWeight; j++) {
                if (j >= weights[i - 1]) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[n][maxWeight];
    }
}