厦门专业的网站制作公司,线上店免费推广的软件,做网站用html,商品分类标准目录 1 基础知识2 模板3 工程化 1 基础知识
#xff08;零#xff09; 背包问题描述#xff1a;有 N N N个物品#xff0c;每个物品的体积是 v i v_i vi#xff0c;价值是 w i w_i wi#xff0c;现有容量是 V V V的背包#xff0c;求这个背包能装下的物品的最大价值… 目录 1 基础知识2 模板3 工程化 1 基础知识
零 背包问题描述有 N N N个物品每个物品的体积是 v i v_i vi价值是 w i w_i wi现有容量是 V V V的背包求这个背包能装下的物品的最大价值。
01背包问题每个物品只有1个。 完全背包问题每个物品有无穷多个。 多重背包问题第 i i i个物品有 s i s_i si个。 分组背包问题有N组物品每组有 s i s_i si个物品但只能选择其中一个。
一 01背包问题讲解。
状态定义f[i][j]从前 i i i个物品中选择总体积不超过 j j j的物品的总价值的最大值。
状态转移
不选择第 i i i个物品即从前 i − 1 i-1 i−1个物品中选择总体积不超过 j j j的物品根据状态的定义可知为f[i-1][j]。选择第 i i i个物品即从前 i − 1 i-1 i−1个物品中选择总体积不超过 j − v [ i ] j-v[i] j−v[i]的物品然后再加上w[i]即f[i-1][j - v[i]] w[i]。
f[i][j]的值取上述两者中的最大值即可。
初始化f[0][0~V]0。
最终答案f[N][V]。
用代码表示如下
#include iostreamusing namespace std;const int N 1010;
int n, m;
int v[N];
int w[N];
int f[N][N];int main() {cin n m;for (int i 1; i n; i) cin v[i] w[i];for (int i 1; i n; i) {for (int j 0; j m; j) {f[i][j] f[i-1][j];if (j v[i]) f[i][j] max(f[i][j], f[i-1][j - v[i]] w[i]);}}cout f[n][m] endl;return 0;
}考虑到上述状态转移过程中在计算第i层的状态时只用到了第i-1层的信息故可以使用滚动数组进行优化将状态表示降成一维的。可以用一个临时数组来存取上一层的状态。更进一步考虑f[i][j] max(f[i][j], f[i-1][j - v[i]] w[i])发现计算f[i][j]时需要知道f[i-1][j-v[i]]的信息而我们可以从jm到jv[i]的顺序进行更新那么使用的就是上一层的f[j-v[i]]故省去了 O ( N ) O(N) O(N)的临时数组的空间。
C代码如下
#include iostreamusing namespace std;const int N 1010;
int n, m;
int v[N];
int w[N];
int f[N];int main() {cin n m;for (int i 1; i n; i) cin v[i] w[i];for (int i 1; i n; i) {for (int j m; j v[i]; --j) {f[j] max(f[j], f[j - v[i]] w[i]);}}cout f[m] endl;return 0;
}二 完全背包问题讲解。
状态定义同上即f[i][j]从前 i i i个物品中选择总体积不超过 j j j的物品的总价值的最大值。
状态转移稍有不同如下
不选第 i i i个物品即f[i-1][j]。选1个第 i i i个物品即f[i-1][j - v[i]] w[i]。选2个第 i i i个物品即f[i-1][j - v[i] * 2] w[i] * 2。 ……选 k k k个第 i i i个物品即f[i-1][j - v[i] * k] w[i] * k。
初始化f[0][0~V]0。
最终答案f[N][V]。
C代码如下
#include iostreamusing namespace std;const int N 1010;
int n, m;
int v[N], w[N];
int f[N][N];int main() {cin n m;for (int i 1; i n; i) cin v[i] w[i];for (int i 1; i n; i) {for (int j 0; j m; j) {for (int k 0; k * v[i] j; k) {f[i][j] max(f[i][j], f[i-1][j - v[i] * k] w[i] * k);}}}cout f[n][m] endl;return 0;
}上述代码的三重循环可以优化到两重循环考虑状态f[i][j]的求解 f [ i ] [ j ] m a x ( f [ i − 1 ] [ j ] , f [ i − 1 ] [ j − v [ i ] ] w [ i ] , f [ i − 1 ] [ j − v [ i ] ∗ 2 ] w [ i ] ∗ 2 , ⋯ , f [ i − 1 ] [ j − v [ i ] ∗ k ] w [ i ] ∗ k ) f[i][j] max(f[i-1][j], \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ f[i-1][j -v[i]] w[i], \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ f[i-1][j - v[i] * 2] w[i] * 2,\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \cdots,\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ f[i-1][j-v[i] * k] w[i] * k) f[i][j]max(f[i−1][j], f[i−1][j−v[i]]w[i], f[i−1][j−v[i]∗2]w[i]∗2, ⋯, f[i−1][j−v[i]∗k]w[i]∗k) 考虑状态f[i][j - v[i]]的求解 f [ i ] [ j − v [ i ] ] m a x ( f [ i − 1 ] [ j − v [ i ] ] , f [ i − 1 ] [ j − v [ i ] ∗ 2 ] w [ i ] , f [ i − 1 ] [ j − v [ i ] ∗ 3 ] w [ i ] ∗ 2 , ⋯ , f [ i − 1 ] [ j − v [ i ] ∗ k ] w [ i ] ∗ k ) f[i][j - v[i]] max(f[i-1][j- v[i]], \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ f[i-1][j -v[i] * 2] w[i], \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ f[i-1][j - v[i] * 3] w[i] * 2,\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cdots,\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ f[i-1][j-v[i] * k] w[i] * k) f[i][j−v[i]]max(f[i−1][j−v[i]], f[i−1][j−v[i]∗2]w[i], f[i−1][j−v[i]∗3]w[i]∗2, ⋯, f[i−1][j−v[i]∗k]w[i]∗k) 观察上式发现有 f [ i ] [ j ] m a x ( f [ i − 1 ] [ j ] , f [ i ] [ j − v [ i ] ] w [ i ] ) f[i][j] max(f[i-1][j], \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ f[i][j-v[i]] w[i]) f[i][j]max(f[i−1][j], f[i][j−v[i]]w[i]) 故写成代码如下
#include iostreamusing namespace std;const int N 1010;
int n, m;
int v[N], w[N];
int f[N][N];int main() {cin n m;for (int i 1; i n; i) cin v[i] w[i];for (int i 1; i n; i) {for (int j 0; j m; j) {f[i][j] f[i-1][j];if (j v[i]) f[i][j] max(f[i][j], f[i][j - v[i]] w[i]);}}cout f[n][m] endl;return 0;
}更进一步可以利用滚动数组进行优化考虑状态f[i][j]的计算公式f[i][j] max(f[i][j], f[i][j - v[i]] w[i])由于此处使用的是第i层的j-v[i]故无需将j从jm到jv[i]这样倒序遍历正序遍历即可。
C代码如下
#include iostreamusing namespace std;const int N 1010;
int n, m;
int v[N], w[N];
int f[N];int main() {cin n m;for (int i 1; i n; i) cin v[i] w[i];for (int i 1; i n; i) {for (int j 0; j m; j) {if (j v[i]) f[j] max(f[j], f[j - v[i]] w[i]);}}cout f[m] endl;return 0;
}三 多重背包问题讲解。
状态定义同一即f[i][j]使用前 i i i个物体且总体积不超过 j j j总价值的最大值。 状态转移
不选择第 i i i个物品即f[i-1][j]。选择1个第 i i i个物品即f[i-1][j-v[i]] w[i]。选择2个第 i i i个物品即f[i-1][j-v[i]*2] w[i]*2 ……选择s[i]个第 i i i个物品即f[i-1][j-v[i]*s[i]] w[i] * s[i]。
C代码如下
#include iostreamusing namespace std;const int N 110;
int n, m;
int v[N], w[N], s[N];
int f[N][N];int main() {cin n m;for (int i 1; i n; i) cin v[i] w[i] s[i];for (int i 1; i n; i) {for (int j 0; j m; j) {for (int k 0; k * v[i] j k s[i]; k) {f[i][j] max(f[i][j], f[i-1][j - v[i] * k] w[i] * k);}}}cout f[n][m] endl;return 0;
}上述时间复杂度为 O ( n ⋅ m ⋅ s ) O(n\cdot m\cdot s) O(n⋅m⋅s)可以优化到 O ( n ⋅ m ⋅ l o g ( s ) ) O(n\cdot m \cdot log(s)) O(n⋅m⋅log(s))。
具体介绍如下考虑到有s[i]个第 i i i类物品可以将其拆成 l o g ( s [ i ] ) log(s[i]) log(s[i])个比如有20个第 i i i类物品可以拆成1个、2个、4个、8个和5个。然后转换成01背包问题。
C代码如下
#include iostreamusing namespace std;const int N 25000, M 2010;
int n, m, cnt;
int v[N], w[N];
int f[M];int main() {cin n m;for (int i 1; i n; i) {int a, b, c;cin a b c;//体积a价值b个数cint k 1;while (c k) {cnt ;v[cnt] k * a;w[cnt] k * b;c - k;k 1;}if (c 0) {cnt;v[cnt] c * a;w[cnt] c * b;}}//做一遍01背包问题for (int i 1; i cnt; i) {for (int j m; j v[i]; --j) {f[j] max(f[j], f[j - v[i]] w[i]);}}cout f[m] endl;return 0;
}四 分组背包问题讲解。
有 N N N组物品每组物品有 s i s_i si类每一类只有一个分别有体积 v i v_i vi、价值 w i w_i wi现在有体积为 V V V的背包只能从每组物品中挑选一个或者不选求背包的最大价值。
状态定义基本同一即f[i][j]从前 i i i个物品中选择总体积不超过 j j j的其最大价值。
状态转移有
不选择第 i i i组物品f[i-1][j]。选择第 i i i组物品中的第0个即f[i-1][j - v[i][0]] w[i][0]。选择第 i i i组物品中的第1个即f[i-1][j - v[i][1]] w[i][1]。 ……选择第 i i i组物品中的第k个即f[i-1][j - v[i][k]] w[i][k]。
C代码如下
#include iostreamusing namespace std;const int N 110;
int n, m;
int s[N];
int v[N][N], w[N][N];
int f[N];int main() {cin n m;for (int i 1; i n; i) {cin s[i];for (int j 0; j s[i]; j) {cin v[i][j] w[i][j];}}for (int i 1; i n; i) {for (int j m; j 0; --j) {for (int k 0; k s[i]; k) {if (v[i][k] j) f[j] max(f[j], f[j - v[i][k]] w[i][k]);}}}cout f[m] endl;return 0;
}2 模板
暂无。。。
3 工程化
暂无。。。
