01背包

2020-06-12 约 1787 字预计阅读 4 分钟次阅读

题目

假设山洞里共有a, b ,c, d ,e这5件宝物（不是5种宝物），它们的重量分别是2, 2, 6, 5, 4，它们的价值分别是6, 3, 5, 4, 6, 现在给你个承重为10的背包, 怎么装背包，可以才能带走最多的财富。

分析

dp问题，先创建dp状态表帮助分析先形式化题目中的一些数据：有m件物品，m=5 背包容量c，c=10 w[i]，第i件物品的重量 v[i]，第i件物品的价值

状态定义 f[i][j]表式i件物品放入容量为j的背包的价值
状态转移方程当没有物品(i=0)或者背包没有剩余空间(j=0)时f[i][j]=0, f[i][j]是最优解，那么f[i-1][j-w[i]]必然也是最优解，现在考虑放入第i件物品，
- 不放则价值不变 f[i][j] = f[i-1][j]
- 放入的话 f[i][j] = f[i-1][j-w[i]] + v[i];

所以有以下状态转移方程 $ f[i][j]= \begin{cases} 0 & if\ min(i,j)=0\\
min \begin{cases} f[i-1][j] \
f[i-1][j-w[i]] + v[i] \end{cases} & otherwise \end{cases} $

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


    public static int knapsack(int m, int c, int[] v, int[] w) {
        int[][] f = new int[m + 1][c + 1];
        // 背包没有剩余空间
        for (int i = 0; i < m + 1; i++) {
            f[i][0] = 0;
        }
        // 没有物品
        for (int j = 0; j < c + 1; j++) {
            f[0][j] = 0;
        }
        for (int i = 1; i < m + 1; i++) {
            for (int j = 1; j < c + 1; j++) {
                // 不放则价值不变 f[i][j] = f[i-1][j-w[i]]
                // 放入的话 f[i][j] = f[i-1][j-w[i]] + v[i];
                if (w[i] <= j) {
                    f[i][j] = Math.max(f[i - 1][j], f[i - 1][j - w[i]] + v[i]);
                } else {
                    f[i][j] = f[i - 1][j];
                }
            }
        }
        return f[m][c];
    }

复杂度分析

时间复杂度和空间复杂度都是O(mn)

空间优化(状态压缩)

对于状态转移方程，考虑到每个F[i][j]都仅和F[i-1][j]或F[i-1][j-v[i]]有关，那么可以通过利用滚动数组的方式，将F[m+1][c+1]所需要空间压缩至f[2][c+1]，从而将空间复杂度降为O(n)。举个例子，我们将f[0][j]状态存在二维表的第0行，接着推出f[1][j]对应的值，并将f[1][j]的状态存放于二维表的第1行。再接着推出f[2][j]的状态时，f[0][j]的状态已经没有保存意义了，因此直接将f[2][j]的状态保存到二维表的第0行，并以此类推，使数组空间得到循环利用。代码实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


    public static int knapsack(int m, int c, int[] v, int[] w) {
        int[][] f = new int[2][c + 1];
        for (int j = 0; j < c + 1; j++) {
            // 初始化第0行最优解
            f[0][j] = 0;
        }
        for (int i = 1; i < m + 1; i++) {
            for (int j = 1; j < c + 1; j++) {
                if (w[i] <= j) {
                    f[i % 2][j] = Math.max(f[(i - 1) % 2][j], f[(i - 1) % 2][j - w[i]] + v[i]);
                } else {
                    f[i % 2][j] = f[(i - 1) % 2][j];
                }
            }
        }
        // f[0]始终保存旧值f[i-1]，f[1]失踪保存新值f[i]
        return f[1][c];
    }

在理解了滚动数组优化空间的基础之上，还可以进一步将长度2*(c+1)的二维表进一步压缩成一个长度为c+1的一维数组s，其状态转移方程为f[j]=max(f[j],f[j-w[i]] + v[i])。这种优化的原理也是非常明显的，先计算F[i-1][j]并存入数组B当中，然后再计算F[i][j]并覆盖数组B中的内容，依次类推直至所有状态求出。由于f[j]可由f[j-w[i]]，即F[i][j]可由F[i-1][j-w[i]]推出，因此在覆盖数组时必须采用倒序存储。举个例子，当你计算出f[0]的状态并覆盖掉原来f[0]中的值时，再要求f[1]时，由于f[0]的值已经发生了改变，所以你无法得到正确的f[1]。代码实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


 public static int knapsack(int m, int c, int[] v, int[] w) {
        int[] f = new int[c + 1];
        for (int j = 0; j < c + 1; j++) {
            // 初始化第0行最优解
            f[j] = 0;
        }
        for (int i = 1; i < m + 1; i++) {
            for (int j = c; j >= 0; j--) {
                if (w[i] <= j) {
                    // 等式右边f[j]上一行的旧值，左边是当前一行的新值，这样滚动覆盖最后的f[j]就是要求的值
                    f[j] = Math.max(f[j], f[j - w[i]] + v[i]);
                }
            }
        }
        return f[c];
    }

然而，不管是滚动数组还是一维数组，在压缩空间的同时，其带来的缺点也很明显，那就是无法通过回溯的方式将所有的最优解求出。若要通过回溯方式求出最优解，那必须对所有的历史状态都进行保留。而压缩存储空间的同时也压缩了问题的解空间，滚动数组的解空间最多仅能容纳2个物品的解，而一维数组的解空间最多只能容纳1个

总结

1、01背包问题属于NP问题之一，每个物品有选和不选两种策略，若采用暴力搜索算法，其时间复杂度为$O(2^n)$，而采用动态规划的方式，则可以将时间复杂度从$O(2^n)$降到$O(n^2)$，通过自底向上逐层递推可以求得最优解 2、在动态规划的过程中，由于其无后效性，往往能够通过对状态转移方程的分析，使用滚动数组的方式压缩存储空间，当当前状态仅仅与前一状态相关时，甚至可以采用一维数组进行进一步压缩，此时需要特别注意数组下标的遍历次序。

目录

01背包

题目

分析

代码

复杂度分析

空间优化(状态压缩)

总结