0-1背包问题Knapsack Problem

发表于 更新于 分类于

背包问题(Knapsack Problem, KP)是NP完全问题，也是一类重要 的组合优化问题 ，在工业 、经济 、通信、金融与计算机 等领域的资 源分配 、 资金预算 、 投资决策 、 装载问题 、 整数规划 、 分布式系统 与密码系统中具有重要的理论和应用价值。

通俗说法

贼，夜入豪宅，可偷之物甚多，而负重能力有限，偷哪些才更加不枉此行？

抽象说法

给定一组多个（[公式]）物品，每种物品都有自己的重量（[公式]）和价值（[公式]），在限定的总重量/总容量（[公式]）内，选择其中若干个（也即每种物品可以选0个或1个），设计选择方案使得物品的总价值最高。

更加抽象的说法

给定正整数[公式]、给定正整数[公式]，求解0-1规划问题：

[公式] ， s.t. [公式] ， [公式] 。

0-1背包问题的递推关系

定义子问题 [公式] 为：在前 [公式] 个物品中挑选总重量不超过 [公式] 的物品，每种物品至多只能挑选1个，使得总价值最大；这时的最优值记作 [公式] ，其中 [公式] ， [公式] 。

考虑第 [公式] 个物品，无外乎两种可能：选，或者不选。

  • 不选的话，背包的容量不变，改变为问题 [公式] ；
  • 选的话，背包的容量变小，改变为问题 [公式] 。

最优方案就是比较这两种方案，哪个会更好些：

[公式] 。

http://static.cyblogs.com/v2-1d8090c991ca13cee3cb43c027b72304_1440w.jpg

得到

[公式] 。

“填二维表”的动态规划方法

[公式] 时才会有“取第 [公式] 件物品”发生。

所以从表格右下角“往回看”如果是“垂直下降”就是发生了 [公式] ，而只有“走斜线”才是“取了”物品。

http://static.cyblogs.com/v2-7bd4c72ec3b5f104e4db3c4aad98cc66_1440w.png

这个算法的复杂度就很容易算了——每一个格子都要填写数字，所以时间复杂度和空间复杂度都是 [公式] 。当” [公式] “时（就不严谨地使用渐近分析的语言了），复杂度是 [公式] 。

手撕Java版本代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
package com.cyblogs.algorithm;

/**
 * Created with leetcode-cn
 *
 * @description: 0-1 背包问题
 * @author: chenyuan
 * @date: 2021/3/29
 * @time: 10:23
 */
public class Knapsack {
    public static void main(String[] args) {
        int N = 6, W = 21;
        // 重量
        int[] w = {0, 2, 3, 4, 5, 9};
        // 价值
        int[] v = {0, 3, 4, 5, 8, 10};
        // 重量 * 价值
        int[][] B = new int[N][W];

        int k,C;
        for (k = 1; k < N; k++) {
            for (C = 1; C < W; C++) {
                if (w[k] > C) {
                    B[k][C] = B[k-1][C];
                } else {
                    // 装进书包
                    int value1 = B[k-1][C-w[k]] + v[k];
                    // 不装进书包
                    int value2 = B[k-1][C];
                    if (value1 > value2) {
                        B[k][C] = value1;
                    } else {
                        B[k][C] = value2;
                    }
                }
            }
        }
        System.out.println(B[5][20]);
    }
}

最后输出的结果是：26。

参考地址