0-1背包问题

0-1背包问题是一个经典的组合优化问题，指在限定的容量下，选择一些物品装入背包，要求装入的物品价值最大。

更具体地，假设有 n 种物品，它们的重量分别为 w1, w2, ..., wn，价值分别为 v1, v2, ..., vn。现在有一个容量为 W 的背包，问如何选择物品装入背包，使得装入的物品总重量不超过背包容量，且总价值最大。

0-1背包问题之所以被称为“0-1”是因为每个物品只有选或不选两种选择，不能部分选择，即要么全部装入，要么全部不装入。

下面我们将介绍一种常见的求解 0-1 背包问题的动态规划算法。

设 dp[i][j] 表示在前 i 种物品中选择若干件物品放入容量为 j 的背包中所能获得的最大价值。则根据上述定义，可得到以下状态转移方程：

当第 i 个物品不放入背包时，dp[i][j] = dp[i-1][j]。 当第 i 个物品放入背包时，dp[i][j] = dp[i-1][j-wi] + vi。 综上，dp[i][j] = max{dp[i-1][j], dp[i-1][j-wi] + vi}。

注意，在以上状态转移方程中，我们将第 i 个物品放入背包中时，其对应的背包容量为 j-wi，而不是 j，因为放入这个物品后，背包中的剩余容量减少了 wi。

最终的结果即为 dp[n][W]。

下面是一个求解 0-1 背包问题的 Java 代码示例：

public static int knapsack01(int[] w, int[] v, int W) {
    int n = w.length;
    int[][] dp = new int[n+1][W+1];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= W; j++) {
            if (j < w[i-1]) {
                dp[i][j] = dp[i-1][j];
            } else {
                dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1]);
            }
        }
    }
    return dp[n][W];
}

在上述代码中，我们使用二维数组 dp 来记录状态。其中 dp[i][j] 表示在前 i 种物品中选择若干件物品放入容量为 j 的背包中所能获得的最大价值。在初始化时，我们将 dp[0][j] 和 dp[i][0] 均设置为 0。在状态转移时，我们根据上述状态转移方程计算 dp[i][j] 的值。

在时间复杂度上，由于需要枚举每个物品以及每个背包容量，因此总时间复杂度为 O(nW)。

需要注意的是，上述代码中的数组索引从 0 开始，而非从 1 开始。这是为了方便计算，因为当 i 或 j 为 0 时，dp[i][j] 始终为 0。因此，为了避免特判 i 或 j 为 0 的情况，我们将数组索引从 0 开始。

此外，当物品重量或价值为实数时，可以使用贪心算法来解决该问题，但贪心算法不一定能得到最优解。

总之，0-1背包问题是一个经典的组合优化问题，可以使用动态规划算法来求解。在实际应用中，也可以使用其他算法，如分支定界算法、贪心算法等。