关于算法:面试官完全背包都不会是你自己走还是我送你

面试官：齐全背包都不会，是你本人走还是我送你？

在现在的面试当中算法题曾经成为面试不可或缺的内容，明天就跟大家分享一个还比拟艰难的口试题——齐全背包。

齐全背包问题

有 $N$ 种物品和一个容量是 $V$ 的背包，每种物品都有 有限件可用。第 $i$ 种物品的体积是 $v_i$，价值是 $w_i$。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

齐全背包问题和 01 背包的惟一区别就在于物品的个数，在 01 背包当中所有的物品只有一件，也就只能应用一次。而在齐全背包当中物品能够应用有限屡次。

比方上面的 4 个物品，背包可能接受的最大分量为 5，咱们应该如何抉择，使得咱们取得的总价值最大：

这个问题还是比较简单，咱们间接从图中看，咱们能够抉择五个 A 或者两个 B 一个A，能够产生最大的收益，最大收益为 10。

齐全背包问题剖析

01 背包动静转移方程剖析

在 01 背包问题当中，咱们是应用一个二维数组 dp[i][j] 进行计算，dp[i][j]示意在只应用前 i 个物品且背包容量为 j 的状况下，咱们可能取得的最大的收益。在这个状况下，咱们依据以后背包容量 j 判断是否能装入第 i 个物品能够失去上面两个方程（上面公式字母的含意与上文齐全背包问题所提到的统一）。

$$
dp[i][j] = \begin{cases}
max(dp[i – 1][j – v[i]] + w[i], dp[i – 1][j]), j \ge v[i]\\
dp[i – 1][j] , j \lt v[i]
\end{cases}
$$

下面 01 背包的公式的第二条比较简单，如果背包容量不足以包容第 i 件物品，那么只能从前 i - 1 物品当中抉择了。咱们来仔细分析一下第一条公式。

如果以后背包容量能够包容第 i 个物品，那么咱们就能够抉择第 i 件物品或者不抉择，咱们应该抉择两种抉择当中收益更大的那个。

• 如果咱们不抉择第 i 个物品，那么咱们就可能应用容量为 j 的背包去抉择前 i - 1 个物品，这种状况下咱们的最大收益为dp[i - 1][j]。
• 如果抉择第 i 个物品，那么咱们背包容量还剩下 j - v[i]，还能够抉择剩下的i - 1 个物品，而且咱们的收益须要加上w[i]，因而咱们的收益为dp[i - 1][j - v[i]] + w[i], dp[i - 1][j])。

齐全背包动静转移方程剖析

和 01 背包问题一样首先对于第 i 个物品，首先须要判断背包是否可能包容：

• 如果背包的容量大于等于第 i 个物品的体积，那咱们就有两种抉择：

  • 将第 i 个物品放入背包当中，然而在这里须要留神的一点是齐全背包的物品有有数件，因而当咱们抉择之后咱们的转移方程为 dp[i][j - v[i]] + w[i]，这里不是i-1 而是 i，因为第i 件物品有有数件。
  • 不将第 i 个物品放入背包当中，那么咱们就可能应用容量为 j 的背包去抉择前 i - 1 个物品，这种状况下咱们的最大收益为dp[i - 1][j]。
• 如果背包容量小于第 i 件物品的体积，咱们就不可能抉择第 i 件物品了，这种状况下咱们的最大收益为dp[i - 1][j]。

基于下面的剖析咱们能够晓得齐全背包问题的动静转移方程为：

$$
dp[i][j] = \begin{cases}
max(dp[i][j – v[i]] + w[i], dp[i – 1][j]), j \ge v[i]\\
dp[i – 1][j] , j \lt v[i]
\end{cases}
$$

背包问题代码形成设计

依据对动静转移方程的剖析，咱们能够晓得，咱们在计算 dp[i][j] 这个数据的值的时候，咱们首先须要将 dp[i][j - v[i]] 和dp[i - 1][j])的后果计算出来，因为 dp[i][j] 依赖这两个数据。

依据下面的剖析和图咱们晓得，在计算 dp[i][j] 之前，咱们须要将第 i 行第 j 列之前的数据和 dp[i - 1][j] 都计算出来，因为 dp[i][j] 依赖这些数据。而咱们最终须要的后果是 dp[N][V] 示意在背包容量为 V 且可能前 N 个物品（也就是所以物品）可能取得的最大的收益，所以咱们最终需要求出 dp[N][V] 的值。

因而基于以上剖析，咱们要想最终解出 dp[N][V] 的值，咱们能够采取两重 for 循环，第一重循环遍历物品，第二重循环遍历容量，然而咱们的第 0 行没有前一行，因而咱们须要对第 0 行进行初始化：

// 对第 0 行进行初始化操作
for (int i = 0; i <= V; ++i) {
    // 如果只能抉择第一个数据，而且能选无数次
    // 那就将所有的容量都拿来装第一个物品
    dp[0][i] = i / v[0] * w[0];
}

依据动静转移方程，咱们有上面的代码：

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

C++残缺代码如下：

#include <iostream>
using namespace std;
#define MAX_LEN 10000

int w[MAX_LEN];
int v[MAX_LEN];
int dp[MAX_LEN][MAX_LEN];
int N, V;

int backpack() {
    // 对第 0 行进行初始化操作
    for (int i = 0; i <= V; ++i) {
        // 如果只能抉择第一个数据，而且能选无数次
        // 那就将所有的容量都哪来装第一个物品
        dp[0][i] = i / v[0] * w[0];
    }
    for (int i = 1; i < N; ++i) {for (int j = 0; j <= V; ++j) {if (j >= v[i]) {dp[i][j] = max(dp[i - 1][j], dp[i][j - v[i]] + w[i]);
            }
            else {dp[i][j] = dp[i - 1][j];
            }
        }
    }
    return dp[N - 1][V];
}

java代码如下：

public static void main(String[] args) {Scanner scanner = new Scanner(System.in);
    int N = scanner.nextInt();
    int V = scanner.nextInt();
    int[] w = new int[N];
    int[] v = new int[N];
    int[][] dp = new int[N][V + 1];
    for (int i = 0; i < N; i++) {v[i] = scanner.nextInt();
        w[i] = scanner.nextInt();}

    // 对第 0 行进行初始化操作
    for (int i = 0; i <= V; ++i) {
        // 如果只能抉择第一个数据，而且能选无数次
        // 那就将所有的容量都哪来装第一个物品
        dp[0][i] = i / v[0] * w[0];
    }

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

齐全背包数组优化

在后面的内容当中咱们曾经仔细分析了齐全背包问题的动静转移方程，咱们发现在两层循环的内层循环当中，必须从 0 遍历到 V，因为咱们前面的数据依赖同一行后面的数据，还有就是依赖上一行雷同列的数据，比方dp[i][j] 依赖 dp[i][0] 到dp[i][j - 1]，还依赖dp[i - 1][j]，这个其实是能够只用一个数组进行计算的。

咱们先来看单行齐全背包的 Java 代码：

public static void main(String[] args) {Scanner scanner = new Scanner(System.in);
    int N = scanner.nextInt();
    int V = scanner.nextInt();
    int[] w = new int[N];
    int[] v = new int[N];
    int[] dp = new int[V + 1];

    for (int i = 0; i < N; i++) {v[i] = scanner.nextInt();
        w[i] = scanner.nextInt();}

    for (int i = 0; i < N; i++) {for (int j = v[i]; j <= V; j++) {dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
        }
    }
    System.out.println(dp[V]);
}

上面咱们举个应用单行数组优化的例子：

如果咱们正在更新 dp[j]，此时dp[j] 还是第 i-1 行的状态而 dp[0] 到dp[j-1]曾经是第 i 行的状态了，因为咱们是从前到后进行遍历。而要计算 dp[j] 的第 i 行状态的后果，那么他须要 dp[0] 到dp[j-1]的第 i 行状态的数据，dp[j]的第 i-1 行状态的数据，而理论状况数组可能满足这种依赖关系，因而咱们能够应用单行数组优化。

这个单行数组与多行数组的区别是多行数组每一行有每一行的状态，而且他保留了所有行的状态，单行数组只存在一行的状态，然而他会经验所有行的状态，也就是在外层 for 循环下单行数组的状态不断更新。（如果你不了解这段话和下面谈到的单行数组优化，能够联合代码和文字进行了解）

C++代码：

#include <iostream>
using namespace std;
#define MAX_LEN 10000

int w[MAX_LEN];
int v[MAX_LEN];
int dp[MAX_LEN]
int N, V;

int backpack() {for (int i = 0; i < N; ++i) {for (int j = v[i]; j <= V; ++j) {dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    }
    return dp[V];
}

int main() {

    cin >> N >> V;
    for (int i = 0; i < N; ++i) {cin >> v[i] >> w[i];
    }
    cout << backpack();
    return 0;
}

总结

在仔细分析完齐全背包问题之后，咱们能够总结一下动静布局的套路：

• 剖析问题设置 dp 数组并剖析数组的含意。
• 寻找动静转移方程，剖析 dp 数组当中数据之间的依赖关系，咱们在迭代的时候肯定要遵循这个关系。
• 初始化数组。
• 进行数组 dp 求解。
• 剖析动静转移方程的含意和数据依赖关系，剖析是否可能在不毁坏数据依赖关系的条件下，优化数组空间。

其实下面的套路对于大多数动静布局的题目都有用的，因为动静布局的流程基本一致，而动静布局最难的中央就是第一步了，通过剖析问题寻找动静转移方程。

以上就是本篇文章的所有内容了，心愿大家有所播种，我是 LeHung，咱们下期再见！！！

更多精彩内容合集可拜访我的项目：https://github.com/Chang-LeHu…

关注公众号：一无是处的钻研僧，理解更多计算机（Java、Python、计算机系统根底、算法与数据结构）常识。