Java 数据结构与算法系列精讲之背包问题

背包问题简介

背包问题是计算机科学中的经典问题，旨在找到最佳的物品组合，使得其总重量不超过背包容量，同时总价值最大化。背包问题有多个变体，每个变体都采用不同的解决方法。

01背包

01背包指的是背包容量固定，并且每个物品只有一个的情况。对于n个物品和一个容量为V的背包，每个物品有两个属性：体积w和价值v。该问题可以由动态规划算法解决，其思路如下：

• 声明一个数组dp[n+1][V+1]，其中dp[i][j]表示前i个物品中选择体积不超过j的最大价值。
• 初始化dp数组的第一行和第一列为0。
• 遍历所有物品，对于第i个物品，从j=1开始往后遍历体积j，若j=w[i]，则可以选择放入第i个物品，此时dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i])，即物品价值的最大值。
• 背包问题的最终解为dp[n][V]。

以下是Java代码示例：

public static int knapsack(int V, int[] w, int[] v, int n) {
    int[][] dp = new int[n+1][V+1];

    for (int i = 0; i <= n; i++) {
        dp[i][0] = 0;
    }
    for (int j = 0; j <= V; j++) {
        dp[0][j] = 0;
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= V; j++) {
            if (j < w[i]) {
                dp[i][j] = dp[i-1][j];
            } else {
                dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]);
            }
        }
    }

    return dp[n][V];
}

完全背包

完全背包指的是背包容量固定，并且每个物品有无限个的情况。与01背包问题不同的是，在每次物品选择时，可以选择不止一个，即选取物品i的数量为k，则物品体积和价值分别为kw[i]和kv[i]。该问题也可以由动态规划算法解决，思路类似于01背包问题：

• 声明一个数组dp[n+1][V+1]，其中dp[i][j]表示前i个物品中选择体积不超过j的最大价值。
• 初始化dp数组的第一行和第一列为0。
• 遍历所有物品，对于第i个物品，从j=w[i]开始往后遍历体积j，若j>=w[i]，则dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]]+v[i])，即物品价值的最大值；若j<w[i]，则dp[i][j] = dp[i-1][j]，即放弃第i个物品。
• 背包问题的最终解为dp[n][V]。

以下是Java代码示例：

public static int knapsack(int V, int[] w, int[] v, int n) {
    int[][] dp = new int[n+1][V+1];

    for (int i = 0; i <= n; i++) {
        dp[i][0] = 0;
    }
    for (int j = 0; j <= V; j++) {
        dp[0][j] = 0;
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= V; j++) {
            if (j >= w[i]) {
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-w[i]]+v[i]);
            } else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }

    return dp[n][V];
}

多重背包

多重背包指的是背包容量固定，并且每个物品最多只有m个的情况。该问题可以看作是01背包问题和完全背包问题的综合，在01背包问题中每个物品有一个，而在完全背包问题中每个物品有无限个，在多重背包中每个物品有m个。该问题也可以由动态规划算法解决，但是因为物品数量较多，所以需要使用优化算法，如单调队列优化等。

以下是Java代码示例：

public static int knapsack(int V, int[] w, int[] v, int[] m, int n) {
    int[] dp = new int[V+1];

    for (int i = 1; i <= n; i++) {
        for (int j = V; j >= w[i]; j--) {
            for (int k = 1; k <= m[i] && k*w[i] <= j; k++) {
                dp[j] = Math.max(dp[j], dp[j-k*w[i]]+k*v[i]);
            }
        }
    }

    return dp[V];
}

示例说明

假设现在有一个容量为10的背包，有以下3个物品：

物品	体积	价值
1	2	3
2	5	7
3	7	9

01背包

对于01背包问题，可以使用以上Java代码求解，得出背包能装下的最大价值为10。

完全背包

对于完全背包问题，同样可以使用以上Java代码，得出背包能装下的最大价值为25。

多重背包

对于多重背包问题，使用以下Java代码可以得出背包能装下的最大价值为28：

int V = 10;
int n = 3;
int[] w = {0, 2, 5, 7};
int[] v = {0, 3, 7, 9};
int[] m = {0, 1, 2, 3};
int res = knapsack(V, w, v, m, n);