背包问题详解

一、背包问题介绍

A. 定义

背包问题是一个经典的组合优化问题，指在给定容量和一组物品的情况下，需要选择一些物品放入容器中，使得总体价值最大化，同时不超过容器的容量限制。

B. 实际应用场景

背包问题在实际生活中具有广泛的应用，如货车或背包装载物品数量和重量的决策、投资组合、硬件资源分配等。

C. 算法求解方式

背包问题可以通过多种算法求解，其中动态规划和贪心算法是解决背包问题的主要方法。在不同场景下可能需要用到不同的算法。

二、01背包问题

A. 问题描述

在一组物品中，每个物品仅有一件，容量和价值是已知的，需要从中选择若干件物品放入背包中，使得背包的容量不超过限制，且所选物品的总价值最大。

B. 解决方案

1. 动态规划算法

使用动态规划算法先求出每个不同容量下的最大价值，再逐步向上推得到全局最优解。时间复杂度为 O(nW)，n表示物品数量，W表示背包容量。

public static int knapsack01DP(int[] volumes, int[] values, int maxVolume) {
    int[][] dp = new int[volumes.length + 1][maxVolume + 1];
    for (int i = 1; i <= volumes.length; i++) {
        for (int j = 1; j <= maxVolume; j++) {
            if (j - volumes[i - 1] >= 0) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - volumes[i - 1]] + values[i - 1]);
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    return dp[volumes.length][maxVolume];
}

2. 贪心算法

使用贪心算法从大到小排序物品，每次选择能放入背包且价值最大的物品放入背包。时间复杂度为 O(nlogn)，其中n表示物品数量。

public static int knapsack01Greedy(int[] volumes, int[] values, int maxVolume) {
    int[] valueDensity = new int[volumes.length];
    for (int i = 0; i < volumes.length; i++) {
        valueDensity[i] = values[i] / volumes[i];
    }
    int maxValue = 0;
    for (int i = 0; i < volumes.length; i++) {
        int maxIndex = getMaxIndex(valueDensity);
        if (maxIndex != -1) {
            if (maxVolume >= volumes[maxIndex]) {
                maxVolume -= volumes[maxIndex];
                maxValue += values[maxIndex];
                valueDensity[maxIndex] = -1;
            } else {
                maxValue += valueDensity[maxIndex] * maxVolume;
                maxVolume = 0;
                break;
            }
        } else {
            break;
        }
    }
    return maxValue;
}

C. 算法复杂度分析

动态规划算法和贪心算法的时间复杂度相比，贪心算法更快，但不能保证得到全局最优解。在某些情况下，贪心算法得到的解可能并不是最优解。

三、完全背包问题

A. 问题描述

在一组物品中，每个物品有无穷个，容量和价值是已知的，需要从中选择若干个物品放入背包中，使得背包的容量不超过限制，且所选物品的总价值最大。

B. 解决方案

1. 动态规划算法

完全背包问题可以看作是01背包问题的扩展，因此可以使用类似的动态规划算法，在算法的内层循环时，将取之前看成不同的状态下取，即可求得最大价值。时间复杂度为 O(nW)。

public static int knapsackFullDP(int[] volumes, int[] values, int maxVolume) {
    int[][] dp = new int[volumes.length + 1][maxVolume + 1];
    for (int i = 1; i <= volumes.length; i++) {
        for (int j = 1; j <= maxVolume; j++) {
            if (j - volumes[i - 1] >= 0) {
                int maxItemCount = j / volumes[i - 1];
                int maxValue = 0;
                for (int k = 0; k <= maxItemCount; k++) {
                    maxValue = Math.max(maxValue, dp[i - 1][j - k * volumes[i - 1]] + k * values[i - 1]);
                }
                dp[i][j] = maxValue;
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    return dp[volumes.length][maxVolume];
}

2. 贪心算法

完全背包问题可以将贪心算法变为一种动态策略算法，选择每一件物品时都基于上一步所花费的容量和本次所花费的容量进行相互参考，选择能放入背包且价值较高的物品进行放置。时间复杂度为O(nlogn)，其中n表示物品数量。

public static int knapsackFullGreedy(int[] volumes, int[] values, int maxVolume) {
    int[] valueDensity = new int[volumes.length];
    for (int i = 0; i < volumes.length; i++) {
        valueDensity[i] = values[i] / volumes[i];
    }
    int maxValue = 0;
    for (int i = 0; i < maxVolume; i++) {
        int maxIndex = getMaxIndex(valueDensity);
        if (maxIndex != -1) {
            if (maxVolume >= volumes[maxIndex]) {
                maxVolume -= volumes[maxIndex];
                maxValue += values[maxIndex];
            } else {
                maxValue += valueDensity[maxIndex] * maxVolume;
                maxVolume = 0;
                break;
            }
        } else {
            break;
        }
    }
    return maxValue;
}

C. 算法复杂度分析

完全背包问题的动态规划算法和01背包问题的动态规划算法非常类似，因此时间复杂度也一样，为 O(nW)。贪心算法的时间复杂度为O(nlogn)。