目录

01背包

题目

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

分析

dp问题, 先创建dp状态表帮助分析 https://gitee.com/lienhui68/picStore/raw/master/null/20200703133733.png 先形式化题目中的一些数据: 有m件物品,m=5 背包容量c,c=10 w[i], 第i件物品的重量 v[i], 第i件物品的价值

  1. 状态定义 f[i][j]表式i件物品放入容量为j的背包的价值

  2. 状态转移方程 当没有物品(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、在动态规划的过程中,由于其无后效性,往往能够通过对状态转移方程的分析,使用滚动数组的方式压缩存储空间,当当前状态仅仅与前一状态相关时,甚至可以采用一维数组进行进一步压缩,此时需要特别注意数组下标的遍历次序。