共计 10728 个字符,预计需要花费 27 分钟才能阅读完成。
背包问题是动静布局算法中十分经典的一类问题,也是口试面试中常见的一类问题。
背包问题有四类:0/ 1 背包问题、齐全背包问题、多重背包问题、混合背包问题。
上面将总结 0/ 1 背包问题、 齐全背包问题 、 多重背包问题 三类问题。对于混合背包问题,难度较大,个别口试面试题也不会过多波及。
笔者自认为本文将背包问题总结地比拟全面,可不免有错漏,欢送批评指正!
一、0/ 1 背包问题
1.1 经典 0 / 1 背包问题
你有一个背包,最多能包容的分量是 m。当初有 n 个物品,第 i 个物品的分量为 w[i] , 价值为 v[i]。求这个背包至少能装多大价值的物品?
本例可参考:NC11【模板】01 背包
动静布局是一个将大问题划分为小问题进行解决,从而一步步获取最优解的过程。对于 0 / 1 背包问题,思考子问题“求解将前 i 个物品放入容量为 j 的背包中的最大价值”,设 F(i, j) 为将前 i 个物品放入容量为 j 的背包中最优解的总价值。对于第 i 个物品,事实上有两种状况:
- w[i] > j,即第 i 个物品的分量大于背包容量 j,则不放入该物品。此时最优解的值等同于将前 i-1 个物品放入容量为 j 的背包中最优解的值,即 F[i][j] = F[i-1][j]。
-
w[i] ≤ j,即第 i 个物品的分量不大于背包容量 j,则有以下两种状况的 最大值 决定:
- 不放入该物品,此时最优解的值等同于将前 i-1 个物品放入容量为 j 的背包中最优解的值,即 F[i][j] = F[i-1][j]。
- 放入该物品,此时背包的 残余容量 为 j-w[i],则最优解的值等同于 “第 i 个物品的价值” 与“前 i-1 个物品放入容量为 j-w[i] 的背包中最优解的值”之和,即 F[i][j] = v[i] + F[i – 1][j – w[i]]。
(留神了解上述过程:是先比拟第 i 个物品的分量与背包容量,若能放,再比拟放入第 i 个物品与不放入第 i 个物品哪个能失去前 i 个物品状况下的最优解!)
因而能够失去递推公式:
$$
初始条件:F(i,0) = F(0, j) = 0 \\
$$
和
$$
F(i,j)=
\begin{cases}
F(i-1, j), & w[i] > j \\
max\{F(i-1,j),v[i] + F(i – 1)(j – w[i]) \}, & w[i] ≤ j
\end{cases}
$$
给出如下一个例子:
背包的承重 m = 5。当初有 4 个物品如下,求背包至少能装多大价值的物品:
物品 分量 价值 1 2 12 2 1 10 3 3 20 4 2 15
对于 n =4, m= 5 的背包问题,应建设一个 dp[n+1][m+1]的二维表。填表过程如下:
你是否对这个填表过程感到相熟?是的,所谓背包问题,其实还是后面的 二维动静布局问题!
填表过程的代码如下:
/**
* @param w 物品的分量
* @param v 物品的价值
* @param n 物品的个数
* @param m 背包的容量
*/
public static int knapsack1(int[] w, int[] v, int n, int m) {int[][] dp = new int[n + 1][m + 1];
for (int i = 1; i < n + 1; i++) {for (int j = 1; j < m + 1; j++) {if (w[i - 1] > j)
dp[i][j] = dp[i - 1][j];
else
dp[i][j] = Math.max(dp[i - 1][j],
v[i - 1] + dp[i - 1][j - w[i - 1]]);
}
}
return dp[n][m];
}
看到这里,你可能会感到纳闷,为什么要这样填表?这样填写进去的表不是与这 n 件物品的存储程序无关吗?然而常识通知咱们,这个问题的解答不应该与物品程序相干呀?
是的,本问题的核心思想就是 “求解将前 i 个物品放入容量为 j 的背包中的最大价值”,而不同的物品程序显然填进去的表是不雷同的。然而,这个动静规划表并不是咱们须要的后果,咱们也并不关怀”前 i 个物品放入容量为 j 的背包“的问题,咱们关怀的是“n 个物品放入容量为 m 的背包”的问题。尽管不同物品程序得出的动静规划表不一样,但其 最优解的值肯定是一样的,而这才是咱们关怀的。
接下来将介绍如何回溯失去最优计划。
1.2 回溯、输入最优解
咱们先用图示的办法看看如何从动静规划表进行回溯、得出最优解的计划:
上述回溯过程仿佛很简单,然而在代码中能够退出一个辅助数组 path[][]来记录更新的物品。则求出最优计划的代码如下:
public static void knapsack2(int[] w, int[] v, int n, int m) {int[][] dp = new int[n + 1][m + 1];
int[][] path = new int[n + 1][m + 1];
for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {if (w[i - 1] > j)
dp[i][j] = dp[i - 1][j];
else {if (dp[i - 1][j] < v[i - 1] + dp[i - 1][j - w[i - 1]]) {dp[i][j] = v[i - 1] + dp[i - 1][j - w[i - 1]];
path[i][j] = 1;
} else {dp[i][j] = dp[i - 1][j];
}
}
}
}
for (int i = n, j = m; i >= 0; i--) {if (path[i][j] == 1) {System.out.println("放入第" + i + "个物品");
j = j - w[i - 1]; // 回溯过程体现在这里!}
}
System.out.println("最大价值为:" + dp[n][m]);
}
上文提到,不同的物品程序失去的动静规划表不同,但最优解的值是雷同的。然而,雷同的只有 最优解的值,因为最优解的计划是须要依据动静布局过程回溯失去的,因而最优解的计划却不肯定一样。
例如将上例中物品 1 的价值批改为 10,求得的最优解尽管同样是 35,却存在 {物品 1, 物品 2, 物品 4} 和 {物品 3, 物品 4} 两个最优计划。你能够应用上面两个例子进行测试:
// 示例 1
int[] w = {2, 1, 3, 2}; // 物品的分量
int[] v = {10, 10, 20, 15}; // 物品的价值
int n = w.length; // 物品的个数
int m = 5; // 背包的容量
knapsack2(w, v, n, m);
// 示例 2
int[] w = {3, 1, 2, 2}; // 物品的分量
int[] v = {20, 10, 10, 15}; // 物品的价值
int n = w.length; // 物品的个数
int m = 5; // 背包的容量
knapsack2(w, v, n, m);
以上两个例子仅仅替换了物品的程序,尽管最优解的值雷同,但最优计划却不同。
那么,怎么判断最优解的计划是否惟一呢?在填表过程中,如果 F[i-1][j] 与 v[i] + F[i – 1][j – w[i]] 相等,则可阐明存在多个最优计划。
1.3 改良 1:记忆性能
注:此办法不需把握,可间接跳过。然而看完之后,置信你会对动静布局有更深一步的理解。
动静布局算法是 自底向上 的:动静布局算法从最小的子问题登程,应用较小子问题的解去填充表格,每个子问题只解一次。然而,有些较小的子问题的解经常不是必须的。
递归的算法是 自顶向下 的:递归算法对递推式的求解将导致须要不止一次地解公共的子问题。例如斐波那契数列问题,递归算法将多次重复计算雷同值,因而效率非常低。
将自底向上的动静布局算法与自顶向下的递归算法联合起来,使它 只对必要的子问题求解 且只求解一次 ,这就是 记忆性能 的办法。该办法自顶向下地应用递归进行求解,但还需保护一个自底向上的动静布局表格:
public class MFKnapsackDemo {public static void main(String[] args) {int[] w = {2, 1, 3, 2}; // 物品的分量
int[] v = {12, 10, 20, 15}; // 物品的价值
int n = w.length; // 物品的数量
int m = 5; // 背包的容量
MFKnapsack mfKnapsack = new MFKnapsack(m, w, v);
System.out.println("最大价值为:" + mfKnapsack.knapsack(n, m));
}
}
class MFKnapsack {
static int n; // 物品的个数
static int m; // 背包的容量
static int[] w; // 物品的分量
static int[] v; // 物品的价值
static int[][] dp; // 动静规划表
/**
* 将 w[]、v[]、dp[][]作为全局变量
* 对于 dp[][],将第 0 行、第 0 列初始化为 0,其余全副初始化为 -1
*/
public MFKnapsack(int m, int[] w, int[] v) {
this.m = m;
this.w = w;
this.v = v;
this.n = w.length;
dp = new int[n + 1][m + 1];
for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {dp[i][j] = -1;
}
}
}
public static int knapsack(int i, int j){if (dp[i][j] < 0){if (j < w[i-1])
dp[i][j] = knapsack(i-1, j);
else
dp[i][j] = Math.max(knapsack(i-1, j), v[i-1] + knapsack(i-1, j-w[i-1]));
}
return dp[i][j];
}
}
递归调用过程不便画出填表的过程,对于该例,其动静规划表 dp[][]为:
比照一般动静布局算法计算出的表格来看,退出记忆性能后,算法将只对必要的子问题进行求解。
然而,退出记忆性能后,它的 工夫效率与惯例的动静布局算法是统一的,退出记忆性能对性能的改良并不会超过一个常数因子。但如果一个值的计算无奈在常数工夫内实现,那么记忆性能对性能的改良可能会更显著。
1.4 改良 2:空间优化
回到经典的 01 背包问题,咱们再看一看外围表达式:
$$
dp[i][j]=
\begin{cases}
dp[i-1][j], & w[i] > j \\
max\{dp[i-1][j],v[i] + dp[i – 1][j – w[i]] \}, & w[i] ≤ j
\end{cases}
$$
能够看到,求解 dp[i][j] 时,其实只须要第 i-1 行的第 j 列或者第 j – w[i] 列的后果,其余行的后果是不须要的。所以咱们真正须要的只有 i-1 这一行,在对 i 遍历时,第 i 层能够主动滚动笼罩掉第 i-1 层。
那么咱们就能够进行空间优化,将其优化为一维数组:
$$
dp[j]=
\begin{cases}
dp[j], & w[i] > j \\
max\{dp[j],v[i] + dp[j – w[i]] \}, & w[i] ≤ j
\end{cases}
$$
如果依照这个公式填表,会发现存在以下问题:
呈现这个问题的起因是:从左向右遍历会导致,后批改的左边的值须要用到先批改的右边的值。
那么如何解决呢?很简略,将其批改为从右向左遍历即可:
依据填表过程,能够失去 01 背包问题的空间优化算法:
public static int knapsack3(int[] w, int[] v, int n, int m) {int[] dp = new int[m + 1];
for (int i = 1; i <= n; i++) {for (int j = m; j >= 1; j--) {//if (w[i - 1] > j) dp[j] = dp[j];
if (w[i - 1] <= j)
dp[j] = Math.max(dp[j], v[i - 1] + dp[j - w[i - 1]]);
}
}
return dp[m];
}
1.5 恰好装满问题
你有一个背包,最多能包容的分量是 m。当初有 n 个物品,第 i 个物品的分量为 w[i] , 价值为 v[i]。若背包 恰好装满,求至少能装多大价值的物品?如果无解请返回 0。
本例可参考:NC11【模板】01 背包
若应用空间优化,则应初始化 dp[0] 为 0,其余初始化为Integer.MIN_VALUE
。
最初若 dp[m] 为负数则阐明恰好装满,若为正数则阐明无解。
对于 NC11【模板】01 背包,给出我的代码:
import java.util.*;
public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[] v = new int[n];
int[] w = new int[n];
for (int i = 0; i < n; i++) {w[i] = sc.nextInt();
v[i] = sc.nextInt();}
int[] dp = new int[m + 1];
for (int i = 1; i <= n; i++) {for (int j = m; j >= 1; j--) {if (w[i - 1] <= j)
dp[j] = Math.max(dp[j], v[i - 1] + dp[j - w[i - 1]]);
}
}
System.out.println(dp[m]);
Arrays.fill(dp, Integer.MIN_VALUE);
dp[0] = 0;
for (int i = 1; i <= n; i++) {for (int j = m; j >= 1; j--) {if (w[i - 1] <= j)
dp[j] = Math.max(dp[j], v[i - 1] + dp[j - w[i - 1]]);
}
}
if (dp[m] < 0) dp[m] = 0;
System.out.print(dp[m]);
}
}
二、齐全背包问题
看到这里先问一下大家,为什么叫做 0/ 1 背包问题 呢?因为在 0 / 1 背包问题中,对于所有的物品只有放与不放两种状况。而 齐全背包问题 就不一样了,在齐全背包问题中,每种物品都有有限件可用:
你有一个背包,最多能包容的分量是 m。当初有 n 种物品,每种物品有任意多个,第 i 个物品的分量为 w[i] , 价值为 v[i]。求这个背包至少能装多大价值的物品?
本例可参考:NC12【模板】齐全背包
2.1 经典齐全背包问题
咱们先看一看 经典 01 背包问题 的方程:
$$
dp[i][j]=
\begin{cases}
dp[i-1][j], & w[i] > j \\
max\{dp[i-1][j],v[i] + dp[i – 1][j – w[i]] \}, & w[i] ≤ j
\end{cases}
$$
对于齐全背包问题,因为每种物品有任意多个,那么咱们能够再退出一层循环 k,k 代表第 i 种物品有 k 件。
则 v[i] 应批改为 k*v[i]
,w[i] 应批改为 k*w[i]
,且应答遍历的 k*v[i]+dp[i-1][j-k*w[i]]
取最大值,因而能够失去 齐全背包问题的方程:
$$
dp[i][j]=
\begin{cases}
dp[i-1][j], & w[i] > j \\
max\{dp[i-1][j], max\{k * v[i] + dp[i – 1][j – k * w[i]]\} \}, & w[i] ≤ k * w[i] ≤ j
\end{cases}
$$
代码如下:
public static int CompleteKnapsack1(int[] w, int[] v, int n, int m) {int[][] dp = new int[n + 1][m + 1];
for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {if (w[i - 1] > j)
dp[i][j] = dp[i - 1][j];
else {for (int k = 1; k <= j / w[i - 1]; k++) {int temp = Math.max(dp[i - 1][j],
k * v[i - 1] + dp[i - 1][j - k * w[i - 1]]);
dp[i][j] = Math.max(dp[i][j], temp);
}
}
}
}
return dp[n][m];
}
然而这种算法的工夫复杂度将达到 O(n^3),性能太差,因而须要进行工夫复杂度的优化。
2.2 改良 1:工夫优化
察看齐全背包问题的方程:
$$
dp[i][j]=
\begin{cases}
dp[i-1][j], & w[i] > j &①\\
max\{dp[i-1][j],max\{k * v[i] + dp[i – 1][j – k * w[i]]\} \}, & w[i] ≤ k * w[i] ≤ j &②
\end{cases}
$$
咱们发现,当 k=0 时,有 dp[i-1][j]
与k*v[i]+dp[i-1][j-k*w[i]]
相等,故以上方程能够合并为:
$$
dp[i][j]=
\begin{cases}
dp[i-1][j], & w[i] > j &①\\
max\{k * v[i] + dp[i – 1][j – k * w[i]] \}, & 0 ≤ k ≤ \frac {j} {w[i]} &②
\end{cases}
$$
对于式子②,咱们晓得有以下两种状况,二者的最大值即为 dp[i][j]:
-
不放入第 i 种物品。则有:
$$
dp[i][j] = dp[i-1][j]
$$ -
放入第 i 种物品。那么应该放入几件呢?由遍历计算得出的最大值决定:
$$
dp[i][j] = max\{k * v[i] + f[i-1][j-k*w[i]] \} \tag{1 ≤ k ≤ j/w[i]}
$$- 用
k+1
替换k
,该式能够写为:
$$
\begin{aligned}
dp[i][j] & = max\{(k+1) * v[i] + f[i-1][j-(k+1)*w[i]] \} \\
& = max\{k * v[i] + f[i-1][j-(k+1)*w[i]] \} +v[i]\\
& = max\{k * v[i] + f[i-1][j-w[i]-k*w[i]] \} +v[i]
\end{aligned}
\\(0 ≤ k ≤ j/w[i])
$$- 对于上述③式,用
j-w[i]
替换j
,该式能够写为:
$$
dp[i][j-w[i]]=max\{k * v[i] + dp[i – 1][j-w[i] – k * w[i]] \} \\(0 ≤ k ≤ j/w[i])
$$-
察看以上两个式子,能够失去:
$$
dp[i][j] = dp[i][j-w[i]] + v[i] \tag{w[i] ≤ j}
$$
- 用
综合不放入的状况与放入的状况,两者应取最大值,因而式子②能够写为:
$$
dp[i][j] = max\{dp[i-1][j], dp[i][j-w[i]] + v[i] \} \tag{w[i] ≤ j}
$$
综上,联合式子①与式子②,因而 齐全背包问题的方程 为:
$$
dp[i][j]=
\begin{cases}
dp[i-1][j], & w[i] > j\\
max\{dp[i-1][j], dp[i][j-w[i]] + v[i] \}, & w[i] ≤ j
\end{cases}
$$
因而能够写出代码:
public static int CompleteKnapsack2(int[] w, int[] v, int n, int m) {int[][] dp = new int[n + 1][m + 1];
for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {if (w[i - 1] > j)
dp[i][j] = dp[i - 1][j];
else
dp[i][j] = Math.max(dp[i - 1][j],
dp[i][j - w[i - 1]] + v[i - 1]);
}
}
return dp[n][m];
}
2.3 改良 2:空间优化
察看 齐全背包问题的方程:
$$
dp[i][j]=
\begin{cases}
dp[i-1][j], & w[i] > j\\
max\{dp[i-1][j], dp[i][j-w[i]] + v[i] \}, & w[i] ≤ j
\end{cases}
$$
能够看到,求解 dp[i][j] 时,其实只须要第 i-1 行的第 j 列或者以后第 i 行曾经求过的第 j-w[i] 列的后果,其余行的后果是不须要的。
那么咱们就能够进行空间优化,将其优化为一维数组:
$$
dp[j]=
\begin{cases}
dp[j], & w[i] > j \\
max\{dp[j],dp[j – w[i]] +v[i]\}, & w[i] ≤ j
\end{cases}
$$
与 0 / 1 背包问题的空间优化不同,因为咱们须要的第 i 行的第 j-w[i] 列在以后值 j 的左侧,因而咱们必须对 j 从左向右遍历 能力取到该值。
因而,空间优化后的齐全背包问题的代码如下:
public static int CompleteKnapsack3(int[] w, int[] v, int n, int m) {int[] dp = new int[m + 1];
for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {if (w[i - 1] <= j)
dp[j] = Math.max(dp[j], dp[j - w[i - 1]] + v[i - 1]);
}
}
return dp[m];
}
2.4 工夫优化的思路转换
下面的工夫优化的的数学过程是不是让你感到很妙又很晕呢?那么咱们换一种思路。
咱们晓得,动静布局是一个将大问题划分为小问题进行解决,从而一步步获取最优解的过程。
咱们将 F[i][j] 示意为“将前 i 个物品放入容量为 j 的背包中的最大价值”,对于第 i 种物品,有两种状况:
- w[i] > j,即第 i 个物品的分量大于背包容量 j。则不放入该物品。此时最优解的值等同于将前 i-1 个物品放入容量为 j 的背包中最优解的值,即 F[i][j] = F[i-1][j]。
-
w[i] ≤ j,即第 i 个物品的分量不大于背包容量 j。则有以下两种状况的 最大值 决定:
- 不放入该物品。此时最优解的值等同于 将前 i-1 个物品放入容量为 j 的背包中的最大价值,即 F[i][j] = F[i-1][j]。
- 放入该物品。先放入一个物品,此物品的价值为 v[i],此时背包的残余容量为 j-w[i]。那么剩下的 j -w[i]应该怎么再放入物品 i 呢?该问题就等同于“将前 i 个物品放入容量为 j-w[i] 的背包中的最大价值”。因而,F[i][j] = v[i] + F[i][j-w[i]]。
因而能够失去递推公式:
$$
dp[i][j]=
\begin{cases}
dp[i-1][j], & w[i] > j\\
max\{dp[i-1][j], dp[i][j-w[i]] + v[i] \}, & w[i] ≤ j
\end{cases}
$$
怎么样?是不是更好了解了呢?
2.5 恰好装满问题
你有一个背包,最多能包容的分量是 m。当初有 n 种物品,每种物品有任意多个,第 i 个物品的分量为 w[i] , 价值为 v[i]。若背包 恰好装满,求至少能装多大价值的物品?如果无解请返回 0。
本例可参考:NC12【模板】齐全背包
若应用空间优化,则应初始化 dp[0] 为 0,其余初始化为Integer.MIN_VALUE
。
最初若 dp[m] 为负数则阐明恰好装满,若为正数则阐明无解。
对于 NC12【模板】齐全背包,给出我的代码:
import java.util.*;
public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[] v = new int[n];
int[] w = new int[n];
for (int i = 0; i < n; i++) {w[i] = sc.nextInt();
v[i] = sc.nextInt();}
int[] dp = new int[m + 1];
for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {if (j >= w[i - 1])
dp[j] = Math.max(dp[j], dp[j - w[i - 1]] + v[i - 1]);
}
}
System.out.println(dp[m]);
Arrays.fill(dp, Integer.MIN_VALUE);
dp[0] = 0;
for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {if (j >= w[i - 1])
dp[j] = Math.max(dp[j], dp[j - w[i - 1]] + v[i - 1]);
}
}
if (dp[m] < 0) dp[m] = 0;
System.out.print(dp[m]);
}
}
三、多重背包问题
你有一个背包,最多能包容的分量是 m。当初有 n 种物品,第 i 个物品的分量为 w[i] , 价值为 v[i],数量为 c[i]。求这个背包至少能装多大价值的物品?
本例可参考:多重背包
3.1 经典多重背包问题
咱们先察看 齐全背包问题的方程:
$$
dp[i][j]=
\begin{cases}
dp[i-1][j], & w[i] > j \\
max\{dp[i-1][j], max\{k * v[i] + dp[i – 1][j – k * w[i]]\} \}, & w[i] ≤ k * w[i] ≤ j
\end{cases}
$$
那么,多重背包与齐全背包的区别在哪里呢?多重背包仅仅是对物品的数量多了个限度k≤c[i]
:
$$
dp[i][j]=
\begin{cases}
dp[i-1][j], & w[i] > j \\
max\{dp[i-1][j], max\{k * v[i] + dp[i – 1][j – k * w[i]]\} \}, & w[i] ≤ k * w[i] ≤ j & and & k ≤ c[i]
\end{cases}
$$
所以,仅仅须要对 k 循环的条件作批改即可。代码如下:
public static int MultipleKnapsack1(int[] w, int[] v, int[] c, int n, int m) {int[][] dp = new int[n + 1][m + 1];
for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {if (w[i - 1] > j)
dp[i][j] = dp[i - 1][j];
else {for (int k = 1; k <= j / w[i - 1] && k <= c[i - 1]; k++) { // 比照齐全背包,仅需批改此处
int temp = Math.max(dp[i - 1][j], k * v[i - 1] + dp[i - 1][j - k * w[i - 1]]);
dp[i][j] = Math.max(dp[i][j], temp);
}
}
}
}
return dp[n][m];
}
3.2 改良 1:空间优化
同样的,多重背包问题能够进行空间优化,其思路与 0 / 1 背包问题统一,须要思考到:若从左向右遍历,会导致后批改的左边的值须要用到先批改的右边的值。
因而,多重背包问题的 j 值须要 从右向左遍历:
public static int MultipleKnapsack2(int[] w, int[] v, int[] c, int n, int m) {int[] dp2 = new int[m + 1];
for (int i = 1; i <= n; i++) {for (int j = m; j >= 1; j--) {if (w[i - 1] <= j) {for (int k = 1; k <= j / w[i - 1] && k <= c[i - 1]; k++) {dp2[j] = Math.max(dp2[j],
k * v[i - 1] + dp2[j - k * w[i - 1]]);
}
}
}
}
return dp[m];
}
3.3 改良 2:二进制优化、枯燥队列优化
多重背包问题还能够进行二进制优化、枯燥队列优化。但笔者满腹经纶,就不多作介绍了。
OJ 地址:多重背包的二进制优化、多重背包的枯燥队列优化
参考资料
- 【尚硅谷】Java 数据结构与算法
- 清华大学出版社《算法设计与剖析根底(第 3 版)》Anany Levitin 著 潘彦 译
- 背包问题 - 笔记整顿