0-1背包问题

题意概要：有n个物品和一个容量为V的背包，每个物品有重量w和价值v两种属性，要求选若干物品放入背包使背包中物品的总价值最大且背包中物品的总重量不超过背包的容量。

首先解释下为什么叫 0-1背包问题 : 在上述例题中，由于每个物体只有两种可能的状态（取与不取），对应二进制中的0和1,这类问题便被称为「0-1 背包问题」

这道题个人觉得是动态规划的敲门砖 , 搞懂了这道题 , 就相当于进了动态规划的大门了

下面写一个表格来明确下 : 设背包容量为6 , 现在有物品如下

	0	1	2	3	4
value	5	10	3	6	3
weight	2	5	1	4	3

总重量限额

	0	1	2	3	4	5	6
0-0
0-1
0-2
0-3						💡
0-4

对于这张二维表 , 每个格子就是 dp[i][j] , 比如说 dp[3][5] , 表示 在 0-3 号物品中 , 选择重量不超过5的物品的最优价值

那么对于这张二维表 , 我们就可以知道 , 这道题的结果就是这个表的最右下角的一个格子的值

这每一个格子就是一个局部问题 , 那我们该如何解出来呢 ?

我们还拿dp[3][5]为例 , 其实它只有两种情况 : 就是到底选不选 3号物品 , 那么有 :

dp[i][j] = max(
    "选第i件物品",
    "不选第i件物品"
)

我们首先来看不选的情况 , 那么以上为例(前4件选择重量不超过5的) , 不选的最优解等同于 同等重量(5)下 , 前3件的最优解 , 即 :

dp[i][j] = max(
    "选第i件物品",
    dp[i-1][j]
)

接下来考虑选择这件物品的情况

如果选择了这件物品 , 它的weight是 w[i], 那么背包剩余的重量为 j-w[i] , 所以我们选了之后再考虑的就是 , 在重量j-w[i]下 , 前3 (i-1) 件的最优解 , 那么有 :

dp[i][j] = max(
    value[i] + dp[i-1][j-w[i]],
    dp[i-1][j]
)

那么核心的部分就结束了 , 接下来稍微考虑下边界情况 , 就是当前背包剩余放不下当前物品时 , 就不用考虑选不选择 , 直接不选 .

下面是代码 :

public class KnapsackProblem {

    public static int knapsack(int[] weights, int[] values, int capacity) {
        int n = weights.length;
        int[][] dp = new int[n + 1][capacity + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= capacity; j++) {
                if (weights[i - 1] > j) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[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 = 8;

        int maxValue = knapsack(weights, values, capacity);
        System.out.println("Maximum value that can be obtained is: " + maxValue);
    }
}