如何使用阿里云做网站上海中高风险地区有哪些

如何使用阿里云做网站,上海中高风险地区有哪些,无锡市网站搭建,网红营销优势目录 ​编辑 前言 一、背包扩展模型的核心逻辑#xff1a;万变不离其宗 二、多重背包#xff1a;物品有使用次数限制的 “精准选择” 2.1 问题定义 2.2 与基础背包的核心区别 2.3 解法一#xff1a;暴力枚举#xff08;基础版#xff09; 2.3.1 思路分析 2.3.2 状…目录​编辑前言一、背包扩展模型的核心逻辑万变不离其宗二、多重背包物品有使用次数限制的 “精准选择”2.1 问题定义2.2 与基础背包的核心区别2.3 解法一暴力枚举基础版2.3.1 思路分析2.3.2 状态表示2.3.3 状态转移方程2.3.4 代码实现暴力版2.3.5 复杂度分析2.4 解法二二进制优化高效版2.4.1 核心优化思想2.4.2 拆分步骤2.4.3 代码实现二进制优化版2.4.4 优化效果2.5 实战案例洛谷 P1077 摆花题目描述分析状态表示状态转移方程代码实现示例输入示例输出解释三、分组背包每组只能选一个的 “互斥选择”3.1 问题定义3.2 核心思路3.3 状态表示与转移状态表示状态转移方程3.4 代码实现基础版3.5 实战案例洛谷 P1757 通天之分组背包题目描述分析代码实现示例输入示例输出解释四、混合背包多种规则并存的 “综合选择”4.1 问题定义4.2 核心思路4.3 代码实现综合版计算过程4.4 实战案例洛谷 P1833 樱花题目描述分析代码实现示例输入示例输出解释五、多维费用背包多重约束下的 “权衡选择”5.1 问题定义5.2 核心思路5.3 代码实现二维费用版5.4 实战案例洛谷 P1910 L 国的战斗之间谍题目描述分析代码实现示例输入示例输出解释六、四大扩展模型对比总结口诀七、常见误区与优化技巧7.1 常见误区7.2 优化技巧总结前言在动态规划的背包世界里01 背包和完全背包是入门的 “敲门砖”但真正的算法实战中问题往往不会这么 “纯粹”—— 物品可能有使用次数限制、可能分成互斥的组、可能同时存在多种选择规则甚至会有多重资源约束。这些复杂场景正是多重背包、分组背包、混合背包和多维费用背包要解决的核心问题。如果你已经掌握了基础背包的逻辑恭喜你接下来这篇文章将带你 “升级打怪”攻克背包问题的四大扩展模型。我们会从实际场景出发拆解每种模型的核心痛点推导状态转移方程提供完整的 C 代码实现还会分享优化技巧和避坑指南。全文干货密集适合有基础背包功底、想进阶提升的算法爱好者。建议收藏后慢慢研读跟着代码敲一遍彻底吃透背包扩展的精髓下面就我们开始吧一、背包扩展模型的核心逻辑万变不离其宗在开始具体模型之前我们先统一一个核心认知所有背包扩展模型本质都是基础背包的 “规则变种”。它们的核心思想始终没变状态表示用dp[j]或多维dp存储 “使用不超过j资源时的最大价值”或其他目标状态转移通过 “选或不选”或 “选几个 / 选哪组”推导当前状态核心目标在资源约束下最大化或最小化某个指标价值、方案数等。变化的只是 “选择规则” 和 “约束条件”多重背包物品有固定使用次数限制分组背包物品分组成互斥集合每组最多选一个混合背包同时存在 01、完全、多重背包的物品多维费用背包资源约束不止一个如体积 重量、时间 金钱。掌握这个 “不变应万变” 的逻辑再学习扩展模型就会事半功倍。接下来我们逐个拆解每种模型。二、多重背包物品有使用次数限制的 “精准选择”2.1 问题定义多重背包的核心约束是每种物品有固定的使用次数上限既不能像 01 背包只能选 1 次也不能像完全背包选无限次。举个生活化的例子你去超市采购背包容量 5L。货架上有 2 种物品物品 1体积 2L价值 10最多 4 件物品 2体积 4L价值 100最多 2 件。请问如何选择才能让背包内物品总价值最大这就是典型的多重背包问题 —— 每个物品的选择次数被限制需要在次数和容量双重约束下做最优决策。2.2 与基础背包的核心区别模型选择次数约束核心差异点01 背包最多 1 次容量枚举从右到左避免重复选择完全背包无限次容量枚举从左到右允许重复选择多重背包最多x[i]次需额外枚举每个物品的使用次数2.3 解法一暴力枚举基础版2.3.1 思路分析多重背包的暴力解法本质是“将多重背包转化为 01 背包”—— 把每个有x[i]次使用限制的物品拆成x[i]个完全相同的 01 背包物品然后用 01 背包的解法求解。比如物品 1 有 4 件就拆成 4 个 “体积 2L、价值 10” 的独立物品再按 01 背包的 “右到左” 枚举容量即可。2.3.2 状态表示dp[j]使用不超过j的容量能获得的最大价值。2.3.3 状态转移方程对于每个物品i枚举其使用次数k0 ≤ k ≤ x[i]且k*v[i] ≤ jdp[j] max(dp[j], dp[j - k*v[i]] k*w[i])k0不选该物品价值不变k0选k件该物品容量消耗k*v[i]价值增加k*w[i]。2.3.4 代码实现暴力版#include iostream #include algorithm #include cstring using namespace std; const int N 110; // 物品数、容量最大值 int n, T; // n物品种数T背包容量 int x[N], w[N], v[N]; // x使用次数上限w价值v体积 int dp[N]; // dp[j]容量j时的最大价值 int main() { // 示例输入2种物品容量8 n 2, T 8; x[1] 4, v[1] 2, w[1] 100; // 物品14件体积2价值100 x[2] 2, v[2] 4, w[2] 100; // 物品22件体积4价值100 memset(dp, 0, sizeof dp); // 多重背包暴力解法枚举物品、容量、使用次数 for (int i 1; i n; i) { // 01背包逻辑容量从右到左 for (int j T; j 0; j--) { // 枚举使用次数k0到x[i]且k*v[i] ≤ j for (int k 1; k x[i] k * v[i] j; k) { dp[j] max(dp[j], dp[j - k * v[i]] k * w[i]); } } } cout 多重背包暴力版最大价值 dp[T] endl; // 输出400 return 0; }2.3.5 复杂度分析时间复杂度O(n*T*max_x)其中max_x是物品的最大使用次数空间复杂度O(T)。优点逻辑简单容易理解适合n、T、max_x都较小的场景如n≤100、T≤100、max_x≤20。缺点效率较低当max_x较大如1e3时会超时。2.4 解法二二进制优化高效版2.4.1 核心优化思想暴力解法的问题在于 “重复枚举相同物品”而二进制优化的核心是用二进制数拆分使用次数x[i]将x[i]个相同物品转化为log2(x[i])个 “超级物品”从而将时间复杂度从O(n*T*max_x)降到O(n*T*log(max_x))。二进制拆分的原理任意整数x都可以拆成2^0, 2^1, 2^2, ..., 2^k, r的形式其中r 2^(k1)这些拆分后的数可以组合出[0, x]区间内的所有整数。比如x9可以拆成1(2^0)、2(2^1)、4(2^2)、2(r9-72)这四个数能组合出 0-9 之间的所有整数如 31251491242。2.4.2 拆分步骤对于物品i使用次数x[i]初始化t1二进制基数当x[i] t时拆出一个 “超级物品”体积t*v[i]价值t*w[i]x[i] - tt * 2若x[i] 0拆出最后一个 “超级物品”体积x[i]*v[i]价值x[i]*w[i]所有 “超级物品” 按 01 背包求解。2.4.3 代码实现二进制优化版#include iostream #include algorithm #include cstring using namespace std; const int N 110 * 5; // 拆分后最大物品数110种物品每种最多拆log2(20)5次 const int M 110; // 背包容量最大值 int n, T; int w[N], v[N], pos; // pos拆分后超级物品的下标 int dp[M]; int main() { n 2, T 8; // 原始物品x[1]4, v2, w100x[2]2, v4, w100 int x[] {0, 4, 2}; int v_ori[] {0, 2, 4}; int w_ori[] {0, 100, 100}; // 二进制拆分 for (int i 1; i n; i) { int cnt x[i]; // 剩余使用次数 int t 1; // 二进制基数 while (cnt t) { pos; v[pos] t * v_ori[i]; w[pos] t * w_ori[i]; cnt - t; t * 2; } // 处理剩余部分 if (cnt 0) { pos; v[pos] cnt * v_ori[i]; w[pos] cnt * w_ori[i]; } } // 01背包求解拆分后的超级物品 memset(dp, 0, sizeof dp); for (int i 1; i pos; i) { for (int j T; j v[i]; j--) { dp[j] max(dp[j], dp[j - v[i]] w[i]); } } cout 多重背包二进制优化版最大价值 dp[T] endl; // 输出400 return 0; }2.4.4 优化效果以x[i]1e3为例暴力枚举需要循环 1e3 次二进制拆分log2(1e3)≈10只需循环 10 次。效率提升非常显著是多重背包的主流优化方法。2.5 实战案例洛谷 P1077 摆花题目链接https://www.luogu.com.cn/problem/P1077题目描述小明的花店门口要摆m盆花有n种花第i种花最多摆a[i]盆。同一种花要放在一起不同种花按标号顺序摆放。求有多少种不同的摆花方案答案对1e67取模。分析这是多重背包的 “方案数” 变种物品n种花容量m盆花约束第i种花最多选a[i]盆目标恰好选m盆的方案数。状态表示dp[j]恰好摆j盆花的方案数。状态转移方程dp[j] (dp[j] dp[j - k]) % MODk第i种花选k盆1 ≤ k ≤ min(a[i], j)初始状态dp[0] 1摆 0 盆花有 1 种方案啥也不摆。代码实现#include iostream #include cstring using namespace std; const int N 110; const int MOD 1e6 7; int n, m; int a[N]; int dp[N]; // dp[j]恰好摆j盆的方案数 int main() { cin n m; for (int i 1; i n; i) { cin a[i]; } memset(dp, 0, sizeof dp); dp[0] 1; // 初始状态 for (int i 1; i n; i) { // 多重背包方案数容量从右到左避免重复计数 for (int j m; j 0; j--) { // 枚举选k盆第i种花 for (int k 1; k a[i] k j; k) { dp[j] (dp[j] dp[j - k]) % MOD; } } } cout dp[m] endl; return 0; }示例输入2 4 3 2示例输出2解释方案 1第 1 种花 3 盆 第 2 种花 1 盆314方案 2第 1 种花 2 盆 第 2 种花 2 盆224。三、分组背包每组只能选一个的 “互斥选择”3.1 问题定义分组背包的核心约束是物品被分成若干组每组中的物品相互互斥最多选择一个。生活化场景你要参加旅行背包容量 5L。物品分成 3 组组 1交通工具自行车体积 2L价值 10、电动车体积 3L价值 15组 2食物面包体积 1L价值 5、巧克力体积 2L价值 8组 3工具帐篷体积 4L价值 20、睡袋体积 3L价值 18。每组最多选一个物品如何选择能让总价值最大这就是分组背包的核心场景 —— 每组内部是“选或不选”但只能选一个组与组之间是“独立选择”。3.2 核心思路分组背包的解法可以概括为“组内 01 背包组间顺序枚举”枚举每组对于每组按 01 背包的 “右到左” 枚举容量避免同一组选多个物品对于每组内的每个物品更新状态。3.3 状态表示与转移状态表示dp[j]使用不超过j的容量选择若干组物品每组最多一个的最大价值。状态转移方程对于第i组的第k个物品体积v价值wdp[j] max(dp[j], dp[j - v] w)前提j v核心同一组内的物品竞争同一容量保证每组最多选一个。3.4 代码实现基础版#include iostream #include algorithm #include vector #include cstring using namespace std; typedef pairint, int PII; // 存储物品的体积和价值 const int N 1010; // 容量最大值 int m, n; // m背包容量n物品总数 vectorPII groups[N]; // groups[i]第i组的所有物品 int dp[N]; int main() { // 示例输入容量453个物品分2组 m 45, n 3; groups[1].push_back({10, 10}); // 组1体积10价值10 groups[1].push_back({10, 5}); // 组1体积10价值5 groups[2].push_back({50, 400});// 组2体积50价值400超容量无法选 memset(dp, 0, sizeof dp); // 分组背包枚举每组 for (int i 1; i 2; i) { // 组内01背包容量从右到左 for (int j m; j 0; j--) { // 枚举组内每个物品 for (auto item : groups[i]) { int v item.first, w item.second; if (j v) { dp[j] max(dp[j], dp[j - v] w); } } } } cout 分组背包最大价值 dp[m] endl; // 输出10 return 0; }3.5 实战案例洛谷 P1757 通天之分组背包题目链接https://www.luogu.com.cn/problem/P1757题目描述有n件物品总重量m。每件物品有重量a[i]、价值b[i]、所属组c[i]。每组内的物品相互冲突最多选一个。求最大利用价值。分析标准分组背包问题只需将物品按组归类然后按分组背包模板求解。代码实现#include iostream #include vector #include algorithm #include cstring using namespace std; typedef pairint, int PII; const int N 1010; int m, n; // m总重量n物品数 vectorPII g[N]; // g[i]第i组的物品重量价值 int dp[N]; int max_group; // 最大组号 int main() { cin m n; for (int i 1; i n; i) { int a, b, c; cin a b c; g[c].push_back({a, b}); max_group max(max_group, c); } memset(dp, 0, sizeof dp); // 枚举每组 for (int i 1; i max_group; i) { // 组内01背包右到左枚举重量 for (int j m; j 0; j--) { for (auto item : g[i]) { int w item.first, val item.second; if (j w) { dp[j] max(dp[j], dp[j - w] val); } } } } cout dp[m] endl; return 0; }示例输入45 3 10 10 1 10 5 1 50 400 2示例输出10解释组 1 的两个物品体积都是 10价值 10 和 5选价值 10 的组 2 的物品体积 5045无法选总价值 10。四、混合背包多种规则并存的 “综合选择”4.1 问题定义混合背包的核心特点是同一问题中同时存在 01 背包、完全背包、多重背包的物品。生活化场景你去商场购物背包容量 10L01 背包物品限量款衣服体积 3L价值 20仅 1 件完全背包物品矿泉水体积 1L价值 2无限供应多重背包物品纸巾体积 2L价值 5最多 3 包。如何选择能让总价值最大混合背包的解法本质是“分类处理”—— 对不同类型的物品采用对应的背包求解逻辑。4.2 核心思路遍历每个物品判断物品类型01、完全、多重对不同类型的物品采用对应的容量枚举顺序和状态转移方式01 背包容量从右到左完全背包容量从左到右多重背包二进制拆分后按 01 背包处理或暴力枚举次数。4.3 代码实现综合版#include iostream #include algorithm #include cstring using namespace std; const int N 1010; // 容量最大值 int V; // 背包容量 int dp[N]; // 处理01背包物品 void zero_one_pack(int v, int w) { for (int j V; j v; j--) { dp[j] max(dp[j], dp[j - v] w); } } // 处理完全背包物品 void complete_pack(int v, int w) { for (int j v; j V; j) { dp[j] max(dp[j], dp[j - v] w); } } // 处理多重背包物品二进制优化 void multiple_pack(int v, int w, int x) { int t 1; while (x t) { zero_one_pack(t * v, t * w); x - t; t * 2; } if (x 0) { zero_one_pack(x * v, x * w); } } int main() { V 10; // 背包容量10 memset(dp, 0, sizeof dp); // 01背包物品衣服v3, w20, x1 zero_one_pack(3, 20); // 完全背包物品矿泉水v1, w2 complete_pack(1, 2); // 多重背包物品纸巾v2, w5, x3 multiple_pack(2, 5, 3); cout 混合背包最大价值 dp[V] endl; // 输出39 return 0; }计算过程衣服3L20 矿泉水5L10 纸巾2L5总容量 35210总价值 2010535优化选择衣服3L20 纸巾 3 包6L15 矿泉水 1 瓶1L2总价值 2015237正确最优解矿泉水 10 瓶10L20不衣服 纸巾 3 包 矿泉水 1 瓶36110价值 2015237实际最优解衣服20 纸巾 3 包15 矿泉水 1 瓶237或矿泉水 10 瓶20显然前者更优。4.4 实战案例洛谷 P1833 樱花题目链接https://www.luogu.com.cn/problem/P1833题目描述爱与愁大神有n棵樱花树每棵树有观赏时间T[i]、美学值C[i]、观赏次数限制P[i]P[i]0表示无限次P[i]0表示最多P[i]次。他从T_s到T_e有m分钟时间求最大美学值。分析标准混合背包问题P[i]0完全背包P[i]101 背包P[i]1多重背包。代码实现#include iostream #include cstring #include algorithm using namespace std; const int N 1e4 10; const int M 1010; // 时间最大值≤1000 int n, m; // n樱花树数m总时间 int t[N], c[N], p[N]; int dp[M]; void zero_one_pack(int v, int w) { for (int j m; j v; j--) { dp[j] max(dp[j], dp[j - v] w); } } void complete_pack(int v, int w) { for (int j v; j m; j) { dp[j] max(dp[j], dp[j - v] w); } } void multiple_pack(int v, int w, int x) { int cnt x; int k 1; while (cnt k) { zero_one_pack(k * v, k * w); cnt - k; k * 2; } if (cnt 0) { zero_one_pack(cnt * v, cnt * w); } } int main() { // 读取时间T_s和T_e转换为分钟差 int h1, m1, h2, m2; char ch; cin h1 ch m1 h2 ch m2 n; m h2 * 60 m2 - (h1 * 60 m1); for (int i 1; i n; i) { cin t[i] c[i] p[i]; } memset(dp, 0, sizeof dp); for (int i 1; i n; i) { if (p[i] 0) { // 完全背包 complete_pack(t[i], c[i]); } else if (p[i] 1) { // 01背包 zero_one_pack(t[i], c[i]); } else { // 多重背包 multiple_pack(t[i], c[i], p[i]); } } cout dp[m] endl; return 0; }示例输入6:50 7:00 3 2 1 0 3 3 1 4 5 4示例输出11解释总时间10 分钟树 1完全背包时间 2价值 1可看 5 次10/25价值 5树 201 背包时间 3价值 3看 1 次价值 3树 3多重背包时间 4价值 5最多 4 次选 1 次4 分钟价值 5最优组合树 23 分钟3 树 34 分钟5 树 13 分钟1.5→1 次1不对正确组合树 3 两次8 分钟10 树 1 一次2 分钟1→ 总价值 11。五、多维费用背包多重约束下的 “权衡选择”5.1 问题定义多维费用背包的核心约束是背包的约束条件不止一个如体积 重量、时间 金钱、人数 空间等。生活化场景你要组织一次露营需要选择物品约束 1背包容量≤10L体积约束约束 2总重量≤15kg重量约束物品帐篷5L8kg价值 20、睡袋3L5kg价值 15、背包2L3kg价值 10。如何选择能让总价值最大多维费用背包的解法本质是 “状态维度扩展”—— 将一维dp[j]扩展为多维dp[j1][j2]...每个维度对应一个约束条件。5.2 核心思路以二维费用背包体积V 重量W为例状态表示dp[j][k]使用不超过j的体积和k的重量能获得的最大价值状态转移对于物品vwval按 01 背包的 “逆序枚举” 更新dp[j][k] max(dp[j][k], dp[j - v][k - w] val)扩展三维及以上费用背包同理扩展状态维度和枚举维度。5.3 代码实现二维费用版#include iostream #include algorithm #include cstring using namespace std; const int V 110; // 体积最大值 const int W 110; // 重量最大值 int dp[V][W]; // dp[j][k]体积j重量k的最大价值 int main() { // 示例输入体积约束10重量约束153个物品 int max_v 10, max_w 15; int items[3][3] { {5, 8, 20}, // 帐篷体积5重量8价值20 {3, 5, 15}, // 睡袋体积3重量5价值15 {2, 3, 10} // 背包体积2重量3价值10 }; memset(dp, 0, sizeof dp); // 二维费用背包01背包逻辑逆序枚举体积和重量 for (int i 0; i 3; i) { int v items[i][0], w items[i][1], val items[i][2]; // 体积逆序 for (int j max_v; j v; j--) { // 重量逆序 for (int k max_w; k w; k--) { dp[j][k] max(dp[j][k], dp[j - v][k - w] val); } } } cout 二维费用背包最大价值 dp[max_v][max_w] endl; // 输出45 return 0; }5.4 实战案例洛谷 P1910 L 国的战斗之间谍题目链接https://www.luogu.com.cn/problem/P1910题目描述有N个人选每个人有资料价值A[i]、伪装能力B[i]越小越差、工资C[i]。敌国探查能力M总伪装能力≤M手头有X元总工资≤X。求能拿到的最大资料价值。分析二维费用背包约束 1总伪装能力≤M约束 2总工资≤X物品每个人01 背包只能选一次目标最大资料价值。代码实现#include iostream #include algorithm #include cstring using namespace std; const int M 1010; // 伪装能力最大值 const int X 1010; // 工资最大值 int dp[M][X]; // dp[j][k]伪装j工资k的最大资料价值 int main() { int N, max_B, max_C; cin N max_B max_C; int A[N1], B[N1], C[N1]; for (int i 1; i N; i) { cin A[i] B[i] C[i]; } memset(dp, 0, sizeof dp); // 二维费用01背包 for (int i 1; i N; i) { int a A[i], b B[i], c C[i]; // 伪装能力逆序 for (int j max_B; j b; j--) { // 工资逆序 for (int k max_C; k c; k--) { dp[j][k] max(dp[j][k], dp[j - b][k - c] a); } } } cout dp[max_B][max_C] endl; return 0; }示例输入3 10 12 10 1 11 1 9 1 7 10 12示例输出11解释选择第 1 个人资料 10伪装 1工资 11 第 2 个人资料 1伪装 9工资 1总伪装1910≤10总工资11112≤12总资料价值10111为最优解。六、四大扩展模型对比总结模型核心约束状态表示核心操作时间复杂度多重背包物品最多选x[i]次一维dp[j]二进制拆分 / 暴力枚举次数O(n*T*log(max_x))分组背包每组最多选一个物品一维dp[j]组内 01 背包右到左枚举O(n*T)混合背包同时存在 01 / 完全 / 多重物品一维dp[j]分类处理按对应模型求解取决于各模型占比多维费用背包多重资源约束如体积 重量多维dp[j1][j2]逆序枚举每个约束维度O(n*T1*T2*...*Tk)口诀多重背包次数有限二进制拆分变 01分组背包组内互斥组间顺序组内逆混合背包规则混杂分类处理各归各多维背包约束多重状态扩维逆序枚举。七、常见误区与优化技巧7.1 常见误区多重背包忘记二进制拆分导致超时分组背包容量枚举顺序错误左到右导致同一组选多个物品混合背包对物品类型判断错误采用了错误的枚举顺序多维背包状态维度顺序搞反或枚举顺序不是逆序导致重复选择。7.2 优化技巧空间优化多维背包可采用 “滚动数组” 优化空间如二维转一维需注意枚举顺序预处理多重背包的二进制拆分可提前完成避免重复计算剪枝对于超出容量的物品直接跳过减少无效枚举数据类型当价值或容量较大时使用long long避免溢出。总结背包问题的扩展模型本质是基础背包逻辑的 “组合” 与 “扩展”。无论是多重背包的次数约束、分组背包的互斥约束、混合背包的规则混杂还是多维背包的多重约束核心都离不开 “状态表示” 和 “状态转移” 这两个动态规划的灵魂。学习这些模型的关键不是死记硬背代码而是理解每种约束对应的 “选择规则”并将其转化为对应的背包逻辑。比如“次数有限” 对应多重背包的二进制拆分“互斥选择” 对应分组背包的组内 01 处理“多重约束” 对应多维状态的扩展。当你能灵活切换不同背包模型的解法甚至能应对多种约束叠加的复杂场景时就真正掌握了背包问题的核心。接下来不妨尝试做一些综合类的背包题目将这些模型融会贯通。如果本文对你有帮助别忘了点赞、收藏、转发三连 有任何疑问或建议欢迎在评论区留言讨论