0-1背包问题的Java动态规划实现

0-1背包问题是经典的动态规划问题,以下是Java实现方案：

问题描述

给定n个物品和一个容量为C的背包，每个物品有重量w[i]和价值v[i]，每个物品只能选择放入或不放入背包,求如何选择物品使背包中物品总价值最大。

动态规划解法

二维数组实现

public class Knapsack {
    public static int knapsack(int[] weights, int[] values, int capacity) {
        int n = weights.length;
        int[][] dp = new int[n + 1][capacity + 1];
        // 初始化dp数组
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 0;
        }
        for (int j = 0; j <= capacity; j++) {
            dp[0][j] = 0;
        }
        // 动态规划填表
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= capacity; j++) {
                if (weights[i - 1] <= j) {
                    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][capacity];
    }
    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);
    }
}

一维数组优化空间复杂度

public class KnapsackOptimized {
    public static int knapsack(int[] weights, int[] values, int capacity) {
        int n = weights.length;
        int[] dp = new int[capacity + 1];
        for (int i = 0; i < n; i++) {
            // 从后向前遍历，避免覆盖还未计算的值
            for (int j = capacity; j >= weights[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
            }
        }
        return dp[capacity];
    }
    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);
    }
}

带物品选择的解法

如果需要知道具体选择了哪些物品,可以添加回溯过程：

public class KnapsackWithItems {
    public static int knapsack(int[] weights, int[] values, int capacity) {
        int n = weights.length;
        int[][] dp = new int[n + 1][capacity + 1];
        boolean[][] selected = new boolean[n + 1][capacity + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= capacity; j++) {
                if (weights[i - 1] <= j) {
                    int valueWith = dp[i - 1][j - weights[i - 1]] + values[i - 1];
                    if (valueWith > dp[i - 1][j]) {
                        dp[i][j] = valueWith;
                        selected[i][j] = true;
                    } else {
                        dp[i][j] = dp[i - 1][j];
                    }
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        // 回溯选择的物品
        int w = capacity;
        System.out.println("选择的物品:");
        for (int i = n; i > 0; i--) {
            if (selected[i][w]) {
                System.out.println("物品" + i + ": 重量=" + weights[i - 1] + ", 价值=" + values[i - 1]);
                w -= weights[i - 1];
            }
        }
        return dp[n][capacity];
    }
    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);
    }
}

复杂度分析

• 时间复杂度：O(n*capacity)，其中n是物品数量，capacity是背包容量
• 空间复杂度：
  • 二维数组实现：O(n*capacity)
  • 一维数组优化：O(capacity)

注意事项

1. 确保weights和values数组长度相同
2. 背包容量和物品重量应为非负整数
3. 一维数组实现时，内层循环必须从后向前遍历，避免重复计算

实现可以解决基本的0-1背包问题,根据实际需求可以选择是否需要记录具体选择的物品。