临沂网站开发公司,中燃oa企业门户,wordpress顶部代码,网站怎么做外链知乎文章目录 一、问题描述二、解决方案1. DP 状态的设计2. 状态转移方程3. 算法复杂度4. 举例5. 实现6. 滚动数组6.1 两行实现6.2 单行实现6.3 优缺点 三、总结 一、问题描述
问题的抽象#xff1a;给定 n n n 种物品和一个背包#xff0c;第 i i i 个物品的体积为 c i c_i … 文章目录 一、问题描述二、解决方案1. DP 状态的设计2. 状态转移方程3. 算法复杂度4. 举例5. 实现6. 滚动数组6.1 两行实现6.2 单行实现6.3 优缺点 三、总结 一、问题描述
问题的抽象给定 n n n 种物品和一个背包第 i i i 个物品的体积为 c i c_i ci价值为 w i w_i wi背包的总容量为 C C C。把物品装入背包时第 i i i 种物品只有两种选择装入背包或不装入背包。如何选择装入背包的物品使装入背包中的物品的总价值最大
具体的问题可以看这道洛谷题P1048 [NOIP2005 普及组] 采药将 物品 换成了 草药将 容量 换成了 时间将 背包的容量 换成了 规定的时间。
二、解决方案
0/1 背包问题 是一道 经典 的使用 动态规划 思想的题目同时也不是很难掌握它之后就正式跨入 动态规划 的大门了。
1. DP 状态的设计
引入一个 ( N 1 ) × ( C 1 ) (N 1) \times (C 1) (N1)×(C1) 的二维数组 d p [ ] [ ] dp[][] dp[][]称为 DP 状态。其中 d p [ i ] [ j ] dp[i][j] dp[i][j] 表示把前 i i i 个从第 1 1 1 个到第 i i i 个物品装入容量为 j j j 的背包中获得的最大价值。
每个 d p [ i ] [ j ] dp[i][j] dp[i][j] 都是一个 0/1 背包问题将前 i i i 个物品装入容量为 j j j 的背包。所以 d p [ N ] [ C ] dp[N][C] dp[N][C] 就代表将前 N N N 个物品装入容量为 C C C 的背包。
2. 状态转移方程
状态转移方程指的是 从一个状态转变到另一个状态的递推公式。
一般使用 自底向上 的 递推 来解决背包问题假设已经递推到 d p [ i ] [ j ] dp[i][j] dp[i][j]分两种情况
第 i i i 个物品的体积比容量 j j j 还大不能装进容量为 j j j 的背包。此时直接继承前 i − 1 i - 1 i−1 个物品装进容量 j j j 的背包的情况即可即 d p [ i ] [ j ] d p [ i − 1 ] [ j ] dp[i][j] dp[i - 1][j] dp[i][j]dp[i−1][j]。第 i i i 个物品的体积比容量 j j j 小能装进背包。此时就体现 0/1 了 0 0 0 表示不装 1 1 1 表示装 装第 i i i 个物品。先在 前 i − 1 i - 1 i−1 个物品装进容量为 j j j 的背包中给第 i i i 个物品空出 c i c_i ci 的空间从而得到背包 d p [ i − 1 ] [ j − c [ i ] ] dp[i - 1][j - c[i]] dp[i−1][j−c[i]]。然后将第 i i i 个物品放入这个背包背包的价值增加 w i w_i wi从而有当前背包 d p [ i ] [ j ] d p [ i − 1 ] [ j − c [ i ] ] w [ i ] dp[i][j] dp[i - 1][j - c[i]] w[i] dp[i][j]dp[i−1][j−c[i]]w[i]。不装第 i i i 个物品。直接继承前 i − 1 i - 1 i−1 个物品装进容量 j j j 的背包的情况即可即 d p [ i ] [ j ] d p [ i − 1 ] [ j ] dp[i][j] dp[i - 1][j] dp[i][j]dp[i−1][j]。此时取这两者中的较大值作为当前背包的价值状态转移方程为 d p [ i ] [ j ] m a x ( d p [ i − 1 ] [ j ] , d p [ i − 1 ] [ j − c [ i ] ] w [ i ] ) dp[i][j] max(dp[i - 1][j], dp[i - 1][j - c[i]] w[i]) dp[i][j]max(dp[i−1][j],dp[i−1][j−c[i]]w[i])
所以 0/1 背包问题 的特征如下
重叠子问题是 d p [ i ] [ j ] dp[i][j] dp[i][j]最优子结构是 d p [ i ] [ j ] dp[i][j] dp[i][j] 的状态转移方程。
3. 算法复杂度
时间复杂度在计算时需要计算二维矩阵 d p [ ] [ ] dp[][] dp[][] 中的每一个值矩阵的大小是 N C NC NC每次计算的时间为 O ( 1 ) O(1) O(1)所以时间复杂度为 O ( N C ) O(NC) O(NC)。空间复杂度使用了大小为 N C NC NC 的二维数组所以空间复杂度为 O ( N C ) O(NC) O(NC)。
说明如果 N , C N, C N,C 很大则 N 1 , C 1 N 1, C 1 N1,C1 可以近似地看作 N , C N, C N,C为了简化所以复杂度不是 O ( ( N 1 ) × ( C 1 ) ) O((N 1) \times (C 1)) O((N1)×(C1))。
4. 举例
初学者可能很难理解这时举一个实际案例就懂了。对于 P1048 题有一个测试用例背包的容量为 70物品的数量为 3物品的体积数组为 [71, 69, 1]物品的价值数组为 [100, 1, 2]。
定义一个 4 * 71 的二维数组如下所示由于长度限制中间的数全部用 ... 代替... 代表的数 和 ... 两边的数相同 先填充索引为 1 的行第一个物品的体积为 71价值为 100 然后填充索引为 2 的行第二个物品的体积为 69价值为 1 接着填充索引为 3 的行第三个物品的体积为 1价值为 2 最终数组的 dp[3][70] 的位置存储着题目的结果——将前 3 个物品放入容量为 70 的背包的最大价值。
5. 实现
// 虽然这些代码看起来是 C 语言的代码但如果选择 C 语言则会编译失败。建议选择 C14
#include stdio.hconst int MAX_N 105; // 最大的物品数量与题目有关
const int MAX_C 1005; // 最大的背包容量与题目有关
int N, C; // N 是物品的数量C 是背包的容量
int c[MAX_N], w[MAX_N]; // c[i], w[i] 分别表示第 i 个物品的 体积 和 价值
int dp[MAX_N][MAX_C]; // dp[i][j] 表示将前 i 个物品装入容量为 j 的背包中// 取 x 和 y 中的较大值
int max(int x, int y) {return x y ? x : y;
}// 进行动态规划
int programming() {for (int i 1; i N; i) {for (int j 1; j C; j) {if (j c[i]) { // 装不下第 i 个物品dp[i][j] dp[i - 1][j];} else { // 能装下第 i 个物品dp[i][j] max(dp[i - 1][j - c[i]] w[i], // 装第 i 个物品dp[i - 1][j] // 不装第 i 个物品);}}}return dp[N][C];
}int main() {// 读取数据scanf(%d %d, C, N);for (int i 1; i N; i) {scanf(%d %d, c[i], w[i]);}// 进行动态规划printf(%d, programming());return 0;
}6. 滚动数组
滚动数组 是 动态规划 最常用的 空间优化技术。动态规划的状态方程通常是二维即以上占用了太多空间用滚动数组可以 极大程度上 减少空间占用它能把 二维 状态方程的空间复杂度优化到 一维更高维的数组也可以通过优化减少一个维度。
从状态转移方程 d p [ i ] [ j ] m a x ( d p [ i − 1 ] [ j ] , d p [ i − 1 ] [ j − c [ i ] ] w [ i ] ) dp[i][j] max(dp[i - 1][j], dp[i - 1][j - c[i]] w[i]) dp[i][j]max(dp[i−1][j],dp[i−1][j−c[i]]w[i]) 中可以看出 d p [ i ] [ ] dp[i][] dp[i][] 只与 d p [ i − 1 ] [ ] dp[i - 1][] dp[i−1][] 有关与之前的 d p [ i − 2 ] [ ] , d p [ i − 3 ] [ ] , ⋯ dp[i - 2][], dp[i - 3][], \cdots dp[i−2][],dp[i−3][],⋯ 都无关。由于它们都没用了索性就 复用 它们占用的空间用新的一行覆盖已经无用的一行只需要两行就够了。这就是“滚动”的含义。
滚动数组根据使用的行数不同分为两种实现方式
6.1 两行实现
仍然使用二维数组不过不是 ( N 1 ) × ( C 1 ) (N 1) \times (C 1) (N1)×(C1) 的二维数组而是 2 × ( C 1 ) 2 \times (C 1) 2×(C1) 的二维数组这就是所谓的“两行”计算 本行 时用 上一行 的结果然后将 本行 和 上一行 互换计算 新的本行新的本行 使用了 原来上一行 的内存空间时使用 新的上一行新的上一行 使用了 原来本行 的内存空间。
#include stdio.hconst int MAX_N 105; // 最大的物品数量与题目有关
const int MAX_C 1005; // 最大的背包容量与题目有关
int N, C; // N 是物品的数量C 是背包的容量
int c[MAX_N], w[MAX_N]; // c[i], w[i] 分别表示第 i 个物品的 体积 和 价值
int dp[2][MAX_C]; // 使用两行滚动数组dp[i][j] 成为不断更新的变量没有固定的含义// 取 x 和 y 中的较大值
int max(int x, int y) {return x y ? x : y;
}// 交换 i 和 j 的值
// 注意 它表示引用传递使用传入的实参而不是重新创建一个新变量来代表实参这是 C 的特性
void swap(int i, int j) {int temp i;i j;j temp;
}// 进行动态规划
int programming() {/*在状态转移方程 dp[i][j] max(dp[i - 1][j], dp[i - 1][j - c[i]] w[i]) 中位于 dp 的行索引的 i 用 curr 来代替i - 1 用 prev 来代替prev, curr 分别是 上一行 和 本行 索引*/int prev 0, curr 1;for (int i 1; i N; i) {swap(prev, curr); // 将本行和上一行互换for (int j 1; j C; j) {if (j c[i]) { // 装不下第 i 个物品dp[curr][j] dp[prev][j];} else { // 能装下第 i 个物品dp[curr][j] max(dp[prev][j - c[i]] w[i], // 装第 i 个物品dp[prev][j] // 不装第 i 个物品);}}}return dp[curr][C]; // 返回当前行的最后一个值
}int main() {// 读取数据scanf(%d %d, C, N);for (int i 1; i N; i) {scanf(%d %d, c[i], w[i]);}// 进行动态规划printf(%d, programming());return 0;
}6.2 单行实现
实际上还能省发现计算 d p [ i ] [ j ] dp[i][j] dp[i][j] 时会用到 d p [ i − 1 ] [ j − c [ i ] ] dp[i - 1][j - c[i]] dp[i−1][j−c[i]] 和 d p [ i − 1 ] [ j ] dp[i - 1][j] dp[i−1][j]所以还可以复用 上一行 中的部分内存空间。
由于 j − c [ i ] j - c[i] j−c[i] 不是一个确定的值取值范围为 [ 0 , j ) [0, j) [0,j)所以 无法 在计算出 d p [ i ] [ j ] dp[i][j] dp[i][j] 的结果前 复用 上一行 中 j j j 之前的内存空间。既然如此就考虑 复用 上一行 中 j j j 之后的内存空间。此时能想到如果 从后向前计算 d p [ i ] [ j ] dp[i][j] dp[i][j]就不会影响 j j j 之前的值。进而就有 单行 的滚动数组实现
#include stdio.hconst int MAX_N 105; // 最大的物品数量与题目有关
const int MAX_C 1005; // 最大的背包容量与题目有关
int N, C; // N 是物品的数量C 是背包的容量
int c[MAX_N], w[MAX_N]; // c[i], w[i] 分别表示第 i 个物品的 体积 和 价值
int dp[MAX_C]; // 使用单行滚动数组dp[j] 成为不断更新的变量没有固定的含义// 取 x 和 y 中的较大值
int max(int x, int y) {return x y ? x : y;
}// 进行动态规划
int programming() {for (int i 1; i N; i) {for (int j C; j 1; j--) { // 切记要从后往前计算if (j c[i]) { // 装不下第 i 个物品dp[j] dp[j];} else { // 能装下第 i 个物品dp[j] max(dp[j - c[i]] w[i], // 装第 i 个物品dp[j] // 不装第 i 个物品);}}}return dp[C]; // 返回单行的最后一个值
}int main() {// 读取数据scanf(%d %d, C, N);for (int i 1; i N; i) {scanf(%d %d, c[i], w[i]);}// 进行动态规划printf(%d, programming());return 0;
}6.3 优缺点
优点优化了空间复杂度很大程度上减少了内存的使用。缺点 由于复用了空间从而覆盖了之前的计算结果数组中的值没有固定的实际含义难以理解通常都是先写出常规的动态规划再使用滚动数组进行优化。还是因为复用了空间导致只留下最后一次计算的状态无法从数组中看出具体的方案。
三、总结
0/1 背包问题 的 0/1 在于每种物品只有两种状态——放进背包 和 不放进背包针对这一问题使用了 动态规划 的解决方案由于空间复杂度比较高所以还使用 滚动数组 的思想进行优化从而将占用的空间 降维。初学者适合用 两行 的实现不容易犯错。熟练掌握动态规划后可以使用 单行 的实现。
