背包问题 (Knapsack Problem)

算法原理

背包问题是一个经典的组合优化问题。给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。0-1背包问题是最基本的背包问题，特点是每个物品只能使用一次，要么装入要么不装入。该问题可以通过动态规划来解决，通过构建一个二维表格来记录在不同容量下能获得的最大价值。

算法步骤

1. 创建一个二维数组dp，其中dp[i][w]表示前i个物品在容量为w的背包中能获得的最大价值
2. 初始化dp数组，第0行和第0列都为0
3. 对于每个物品i和每个容量w，计算：
   • 如果不装入物品i，则dp[i][w] = dp[i-1][w]
   • 如果装入物品i（前提是容量足够），则dp[i][w] = dp[i-1][w-weight[i]] + value[i]
   • 取两者的最大值作为dp[i][w]
4. dp[n][W]即为所求的最大价值
5. 通过回溯dp数组可以找出具体选择了哪些物品

代码实现

public class Knapsack {
    // 0-1背包问题解决方案
    public static int knapsack(int capacity, int[] weights, int[] values, int n) {
        // 创建dp表
        int[][] dp = new int[n + 1][capacity + 1];
        
        // 填充dp表
        for (int i = 1; i <= n; i++) {
            for (int w = 1; w <= capacity; w++) {
                // 如果当前物品的重量超过背包容量，则不能装入
                if (weights[i - 1] > w) {
                    dp[i][w] = dp[i - 1][w];
                } else {
                    // 比较装入和不装入当前物品的价值
                    int valueWithItem = values[i - 1] + dp[i - 1][w - weights[i - 1]];
                    int valueWithoutItem = dp[i - 1][w];
                    dp[i][w] = Math.max(valueWithItem, valueWithoutItem);
                }
            }
        }
        
        return dp[n][capacity];
    }
    
    // 优化空间复杂度的版本
    public static int knapsackOptimized(int capacity, int[] weights, int[] values, int n) {
        // 使用一维数组优化空间
        int[] dp = new int[capacity + 1];
        
        // 填充dp数组
        for (int i = 1; i <= n; i++) {
            // 注意这里是逆序遍历，避免重复使用同一物品
            for (int w = capacity; w >= weights[i - 1]; w--) {
                dp[w] = Math.max(dp[w], dp[w - weights[i - 1]] + values[i - 1]);
            }
        }
        
        return dp[capacity];
    }
    
    // 返回具体的物品选择方案
    public static void knapsackWithPath(int capacity, int[] weights, int[] values, int n) {
        int[][] dp = new int[n + 1][capacity + 1];
        
        // 填充dp表
        for (int i = 1; i <= n; i++) {
            for (int w = 1; w <= capacity; w++) {
                if (weights[i - 1] > w) {
                    dp[i][w] = dp[i - 1][w];
                } else {
                    int valueWithItem = values[i - 1] + dp[i - 1][w - weights[i - 1]];
                    int valueWithoutItem = dp[i - 1][w];
                    dp[i][w] = Math.max(valueWithItem, valueWithoutItem);
                }
            }
        }
        
        // 回溯找出选择的物品
        System.out.println("最大价值: " + dp[n][capacity]);
        System.out.println("选择的物品:");
        
        int w = capacity;
        for (int i = n; i > 0 && dp[i][w] > 0; i--) {
            // 如果dp[i][w] != dp[i-1][w]，说明选择了第i个物品
            if (dp[i][w] != dp[i - 1][w]) {
                System.out.println("物品 " + i + " (重量: " + weights[i - 1] + 
                                   ", 价值: " + values[i - 1] + ")");
                w -= weights[i - 1];
            }
        }
    }

    // 测试方法
    public static void main(String[] args) {
        // 物品的重量和价值
        int[] weights = {2, 1, 3, 2};
        int[] values = {12, 10, 20, 15};
        int capacity = 5;  // 背包容量
        int n = weights.length;  // 物品数量
        
        System.out.println("物品信息:");
        for (int i = 0; i < n; i++) {
            System.out.println("物品 " + (i + 1) + ": 重量=" + weights[i] + 
                               ", 价值=" + values[i] + ", 性价比=" + 
                               (double) values[i] / weights[i]);
        }
        System.out.println("背包容量: " + capacity);
        
        int maxValue = knapsack(capacity, weights, values, n);
        System.out.println("\n使用标准DP方法，最大价值: " + maxValue);
        
        int maxValueOpt = knapsackOptimized(capacity, weights, values, n);
        System.out.println("使用优化DP方法，最大价值: " + maxValueOpt);
        
        System.out.println("\n详细选择方案:");
        knapsackWithPath(capacity, weights, values, n);
    }
}

应用场景

• 资源分配：在有限资源下最大化收益
• 投资决策：在预算限制下选择投资项目
• 货物装载：在载重限制下装载最有价值的货物
• 任务调度：在时间限制下选择最有价值的任务
• 组合优化：各种需要在约束条件下优化选择的问题

优缺点