石家庄云图网站建设网站开发版本号

石家庄云图网站建设,网站开发版本号,泗洪县建设局网站怎么查不到,开发公司如何加强财务管理目录 前言 一、背包问题的本质#xff1a;资源分配的最优解 二、01 背包#xff1a;每个物品只能选一次的 “取舍艺术” 2.1 问题定义 2.2 暴力解法的困境 2.3 动态规划解法#xff1a;从二维到一维 2.3.1 第一步#xff1a;定义状态 2.3.2 第二步#xff1a;推导…目录前言一、背包问题的本质资源分配的最优解二、01 背包每个物品只能选一次的 “取舍艺术”2.1 问题定义2.2 暴力解法的困境2.3 动态规划解法从二维到一维2.3.1 第一步定义状态2.3.2 第二步推导状态转移方程2.3.3 第三步初始化2.3.4 第四步填表顺序2.3.5 代码实现二维版本2.3.6 空间优化从二维到一维核心观察状态重定义关键修改容量枚举顺序优化后的状态转移方程一维版本代码实现2.4 01 背包的变体恰好装满背包核心思路代码实现恰好装满版本2.5 实战案例洛谷 P1048 采药题目描述输入分析代码实现示例输入示例输出解释三、完全背包每个物品可以选无限次的 “贪心博弈”3.1 问题定义3.2 与 01 背包的核心区别3.3 动态规划解法从二维到一维3.3.1 第一步定义状态3.3.2 第二步推导状态转移方程3.3.3 空间优化一维数组3.3.4 代码实现一维版本3.4 完全背包的变体恰好装满背包代码实现3.5 实战案例洛谷 P1616 疯狂的采药题目描述输入分析代码实现示例输入示例输出解释四、01 背包与完全背包的对比总结关键口诀五、常见误区与注意事项5.1 状态定义混淆5.2 容量枚举顺序错误5.3 数据溢出问题5.4 初始化错误总结在算法世界里动态规划DP绝对是 “让人又爱又恨” 的存在 —— 它像一把万能钥匙能解开无数复杂的多阶段决策问题但入门时的晦涩难懂又让很多初学者望而却步。而在动态规划的庞大体系中背包问题无疑是最经典、最核心的分支没有之一。无论是面试高频题还是算法竞赛中的基础模块背包问题都占据着举足轻重的地位。它的核心思想 ——“拆分问题、存储子问题解、避免重复计算”不仅适用于背包本身更能迁移到字符串匹配、路径规划、资源分配等诸多场景。今天我们就来深入剖析背包问题的两大基础模型01 背包和完全背包。这篇文章不会一上来就抛公式、堆代码而是从实际场景出发带你一步步拆解问题、定义状态、推导方程再通过优化技巧提升效率。无论你是刚接触 DP 的新手还是想巩固基础的老手相信都能有所收获。现在就让我们正式开始吧一、背包问题的本质资源分配的最优解在聊具体模型之前我们先搞懂一个核心问题什么是背包问题通俗来讲背包问题的本质是“有限资源下的最优选择”。想象一个场景你有一个容量有限的背包面前有一堆物品每个物品都有自己的重量或体积和价值。你需要决定选哪些物品放入背包在不超过背包容量的前提下让背包内物品的总价值最大。这个场景可以衍生出多种变体每个物品只能选一次01 背包每个物品可以选无限次完全背包每个物品可以选有限次多重背包物品分成几组每组只能选一个分组背包除了重量还有体积等多个限制条件多维背包。而我们今天要讲的 01 背包和完全背包是所有变体的基础 —— 吃透这两个模型再学习其他变体就会水到渠成。在正式开始前我们先统一几个约定避免后续混淆背包容量通常用V表示也可能是时间、金钱等资源物品数量通常用n表示第i个物品的重量或消耗的资源v[i]第i个物品的价值w[i]动态规划数组dp[j]表示 “使用不超过j的资源时能获得的最大价值”后续会详细解释状态定义。二、01 背包每个物品只能选一次的 “取舍艺术”2.1 问题定义01 背包的核心约束是每个物品要么选1 次要么不选0 次不存在选多次的情况。举个生活化的例子你要去旅行背包容量是 5L。面前有 3 件物品物品 1体积 2L价值 10一本绝版书物品 2体积 4L价值 5一个普通水杯物品 3体积 1L价值 4一个充电宝。请问如何选择物品才能让背包内物品的总价值最大这就是典型的 01 背包问题 —— 每个物品只能带一件你需要在容量限制下做最优取舍。2.2 暴力解法的困境首先我们想想最直接的暴力解法枚举所有可能的选择组合计算每个组合的总重量和总价值筛选出符合容量限制的最大价值。对于n个物品总共有2^n种组合每个物品都有选或不选两种状态。当n10时组合数是 1024当n20时组合数就达到了 100 多万当n30时更是突破 10 亿 —— 显然暴力解法在n稍大时就会超时完全不可行。这时候动态规划的优势就体现出来了通过存储子问题的解避免重复计算将时间复杂度从O(2^n)降到O(nV)让问题变得可解。2.3 动态规划解法从二维到一维2.3.1 第一步定义状态动态规划的核心是 “状态表示”—— 我们需要用一个数组来存储子问题的解。对于 01 背包最直观的状态定义是二维数组dp[i][j]从前i个物品中选择且总重量不超过j时能获得的最大价值。这个定义包含两个关键信息选择范围前i个物品不考虑后面的物品资源限制总重量≤j目标最大价值。有了这个状态定义我们的最终答案就是dp[n][V]—— 从前n个物品中选择总重量不超过V的最大价值。2.3.2 第二步推导状态转移方程状态转移方程是动态规划的 “灵魂”它描述了子问题之间的递推关系。对于dp[i][j]我们可以根据 “第i个物品是否被选择” 分为两种情况不选第i个物品此时的最大价值就等于“从前i-1个物品中选择总重量不超过j的最大价值”即dp[i][j] dp[i-1][j]选第i个物品此时需要满足j ≥ v[i]背包容量足够装下第i个物品。选择后背包剩余容量为j - v[i]最大价值等于 “从前i-1个物品中选择总重量不超过j - v[i]的最大价值” 加上第i个物品的价值即dp[i][j] dp[i-1][j - v[i]] w[i]。综合两种情况状态转移方程为dp[i][j] max(dp[i-1][j], (j v[i] ? dp[i-1][j - v[i]] w[i] : 0))简单理解对于每个物品和每个容量我们都在 “选” 和 “不选” 之间做最优决策取两者的最大值。2.3.3 第三步初始化初始化的目的是设置 “边界条件”让递推能够正常开始。对于二维数组dp当i0没有物品可选时无论j是多少最大价值都是 0即dp[0][j] 0当j0背包容量为 0无法装任何物品时无论i是多少最大价值都是 0即dp[i][0] 0。2.3.4 第四步填表顺序二维数组的填表顺序很直观先枚举物品从 1 到n再枚举容量从 1 到V。因为dp[i][j]只依赖于dp[i-1][...]前i-1个物品的状态所以按行填表即可保证每个状态都能通过已计算的状态推导得出。2.3.5 代码实现二维版本我们用前面的旅行背包例子来实现二维版本的 01 背包#include iostream #include algorithm using namespace std; const int N 1010; // 物品数量和背包容量的最大值 int n, V; // n物品数V背包容量 int v[N], w[N]; // v物品重量w物品价值 int dp[N][N]; // 二维dp数组 int main() { // 输入数据3个物品背包容量5 n 3, V 5; v[1] 2, w[1] 10; // 物品1体积2价值10 v[2] 4, w[2] 5; // 物品2体积4价值5 v[3] 1, w[3] 4; // 物品3体积1价值4 // 初始化dp[0][j]和dp[i][0]默认都是0可省略显式初始化 // 填表枚举物品和容量 for (int i 1; i n; i) { for (int j 1; j V; j) { // 不选第i个物品 dp[i][j] dp[i-1][j]; // 选第i个物品如果容量足够 if (j v[i]) { dp[i][j] max(dp[i][j], dp[i-1][j - v[i]] w[i]); } } } // 输出结果dp[3][5] 14选物品1和物品310414 cout 二维版本01背包最大价值 dp[n][V] endl; return 0; }运行结果14与我们手动计算的最优解一致。2.3.6 空间优化从二维到一维二维版本的时间复杂度是O(nV)空间复杂度也是O(nV)。当n和V都达到 1000 时数组大小是 1e6完全可以接受但如果V达到 1e51e8 的数组大小就会超出内存限制。因此我们需要进行空间优化 —— 将二维数组压缩为一维数组。核心观察在二维数组中dp[i][j]只依赖于dp[i-1][...]上一行的状态而不依赖于dp[i][...]当前行的状态。这意味着我们可以用一个一维数组dp[j]来存储状态每次更新时覆盖旧值。状态重定义dp[j]当前考虑到第i个物品时总重量不超过j的最大价值。关键修改容量枚举顺序如果我们仍然按 “从左到右” 的顺序枚举容量会出现一个问题当计算dp[j]时dp[j - v[i]]已经被当前行第i个物品更新过了这会导致同一个物品被多次选择变成完全背包的逻辑。为了避免这个问题我们需要将容量枚举顺序改为从右到左从V到v[i]。这样当计算dp[j]时dp[j - v[i]]仍然是上一行第i-1个物品的状态保证了每个物品只被选择一次。优化后的状态转移方程for (int i 1; i n; i) { // 从右到左枚举容量 for (int j V; j v[i]; j--) { dp[j] max(dp[j], dp[j - v[i]] w[i]); } }一维版本代码实现#include iostream #include algorithm #include cstring using namespace std; const int N 1010; int n, V; int v[N], w[N]; int dp[N]; // 一维dp数组 int main() { n 3, V 5; v[1] 2, w[1] 10; v[2] 4, w[2] 5; v[3] 1, w[3] 4; // 初始化dp[j]默认都是0 memset(dp, 0, sizeof dp); // 填表枚举物品从右到左枚举容量 for (int i 1; i n; i) { for (int j V; j v[i]; j--) { dp[j] max(dp[j], dp[j - v[i]] w[i]); } } cout 一维版本01背包最大价值 dp[V] endl; return 0; }运行结果同样是14但空间复杂度从O(nV)降到了O(V)优化效果显著。2.4 01 背包的变体恰好装满背包在实际问题中有时会要求 “背包恰好装满”此时的解法需要对初始化和结果判断做一些修改。核心思路初始化时只有dp[0] 0容量为 0 时恰好装满的价值为 0其他dp[j]都初始化为-∞表示该容量无法恰好装满状态转移方程不变最终结果如果dp[V] 0说明无法恰好装满背包输出 0否则输出dp[V]。代码实现恰好装满版本#include iostream #include algorithm #include cstring using namespace std; const int N 1010; const int INF 0x3f3f3f3f; // 表示无穷大 int n, V; int v[N], w[N]; int dp[N]; int main() { n 3, V 5; v[1] 2, w[1] 10; v[2] 4, w[2] 5; v[3] 1, w[3] 4; // 初始化dp[0] 0其他为-∞ memset(dp, -INF, sizeof dp); dp[0] 0; // 填表 for (int i 1; i n; i) { for (int j V; j v[i]; j--) { if (dp[j - v[i]] ! -INF) { // 确保前一个状态合法 dp[j] max(dp[j], dp[j - v[i]] w[i]); } } } // 结果判断如果dp[V] 0说明无法恰好装满 int res dp[V] 0 ? 0 : dp[V]; cout 01背包恰好装满的最大价值 res endl; return 0; }在上面的例子中背包容量 5 能否恰好装满我们看看可能的组合物品 12L 物品 31L 3L未满物品 24L 物品 31L 5L恰好装满价值 549物品 1 物品 26L超容。因此运行结果为9符合预期。2.5 实战案例洛谷 P1048 采药题目链接https://www.luogu.com.cn/problem/P1048题目描述辰辰是个天资聪颖的孩子他的梦想是成为世界上最伟大的医师。为此他想拜附近最有威望的医师为师。医师为了判断他的资质给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说“孩子这个山洞里有一些不同的草药采每一株都需要一些时间每一株也有它自身的价值。我会给你一段时间在这段时间里你可以采到一些草药。如果你是一个聪明的孩子你应该可以让采到的草药的总价值最大。”输入第一行有两个整数T总共能用来采药的时间和M草药的数目。接下来M行每行包括两个整数分别表示采摘某株草药的时间和价值。分析这是一道典型的 01 背包问题 —— 每个草药只能采一次01时间就是背包容量价值就是草药的价值。代码实现#include iostream #include algorithm #include cstring using namespace std; const int N 1010; // T最大为1000 int T, M; // T总时间M草药数 int t[N], w[N]; // t采药时间w草药价值 int dp[N]; // dp[j]用不超过j的时间能获得的最大价值 int main() { cin T M; for (int i 1; i M; i) { cin t[i] w[i]; } // 初始化dp[j]默认0 memset(dp, 0, sizeof dp); // 01背包一维解法 for (int i 1; i M; i) { for (int j T; j t[i]; j--) { dp[j] max(dp[j], dp[j - t[i]] w[i]); } } cout dp[T] endl; return 0; }示例输入70 3 71 100 69 1 1 2示例输出3解释总时间 703 种草药草药 1时间 7170无法采摘草药 2时间 69价值 1草药 3时间 1价值 2最优选择采摘草药 269 时间价值 1 草药 31 时间价值 2总时间 70总价值 3。三、完全背包每个物品可以选无限次的 “贪心博弈”3.1 问题定义完全背包的核心约束是每个物品可以选择无限次只要背包容量足够。还是用旅行背包的例子假设物品可以无限选背包容量 5L物品 1体积 2L价值 10物品 2体积 4L价值 5物品 3体积 1L价值 4。此时的最优解是什么显然是选 5 个物品 35×1L5L总价值 5×420这就是完全背包的逻辑。3.2 与 01 背包的核心区别完全背包和 01 背包的唯一区别的是物品的选择次数01 背包每个物品最多选 1 次 → 容量枚举必须从右到左避免重复选择完全背包每个物品可以选无限次 → 容量枚举必须从左到右允许重复选择。这个区别直接导致了两者在代码上的唯一差异 ——容量枚举顺序的不同。3.3 动态规划解法从二维到一维3.3.1 第一步定义状态完全背包的状态定义和 01 背包完全一致二维版本dp[i][j]表示从前i个物品中选择总重量不超过j时的最大价值一维版本dp[j]表示当前考虑到第i个物品时总重量不超过j的最大价值。3.3.2 第二步推导状态转移方程对于完全背包的二维版本状态转移方程为dp[i][j] max(dp[i-1][j], (j v[i] ? dp[i][j - v[i]] w[i] : 0))注意和 01 背包的区别选第i个物品时依赖的是dp[i][j - v[i]]当前行的状态而不是dp[i-1][j - v[i]]上一行的状态。这是因为选择第i个物品后还可以继续选择它无限次。3.3.3 空间优化一维数组由于二维版本中dp[i][j]依赖于dp[i][j - v[i]]当前行的左侧状态因此一维版本的容量枚举顺序需要改为从左到右从v[i]到V。这样当计算dp[j]时dp[j - v[i]]已经是当前行更新后的值相当于已经考虑了多次选择第i个物品的情况。优化后的状态转移方程for (int i 1; i n; i) { // 从左到右枚举容量 for (int j v[i]; j V; j) { dp[j] max(dp[j], dp[j - v[i]] w[i]); } }3.3.4 代码实现一维版本我们用之前的旅行背包例子实现完全背包#include iostream #include algorithm #include cstring using namespace std; const int N 1010; int n, V; int v[N], w[N]; int dp[N]; int main() { n 3, V 5; v[1] 2, w[1] 10; v[2] 4, w[2] 5; v[3] 1, w[3] 4; memset(dp, 0, sizeof dp); // 完全背包从左到右枚举容量 for (int i 1; i n; i) { for (int j v[i]; j V; j) { dp[j] max(dp[j], dp[j - v[i]] w[i]); } } cout 完全背包最大价值 dp[V] endl; return 0; }运行结果20与我们手动计算的最优解5 个物品 3价值 20一致。3.4 完全背包的变体恰好装满背包和 01 背包类似完全背包也可以要求 “恰好装满”解法同样是修改初始化dp[0] 0容量 0 恰好装满价值 0其他dp[j] -∞无法恰好装满最终结果若dp[V] 0输出 0否则输出dp[V]。代码实现#include iostream #include algorithm #include cstring using namespace std; const int N 1010; const int INF 0x3f3f3f3f; int n, V; int v[N], w[N]; int dp[N]; int main() { n 3, V 5; v[1] 2, w[1] 10; v[2] 4, w[2] 5; v[3] 1, w[3] 4; memset(dp, -INF, sizeof dp); dp[0] 0; for (int i 1; i n; i) { for (int j v[i]; j V; j) { if (dp[j - v[i]] ! -INF) { dp[j] max(dp[j], dp[j - v[i]] w[i]); } } } int res dp[V] 0 ? 0 : dp[V]; cout 完全背包恰好装满的最大价值 res endl; return 0; }运行结果205 个物品 3 恰好装满 5L价值 20。3.5 实战案例洛谷 P1616 疯狂的采药题目链接https://www.luogu.com.cn/problem/P1616题目描述LiYuxiang 是个天资聪颖的孩子他的梦想是成为世界上最伟大的医师。为此他想拜附近最有威望的医师为师。医师为了判断他的资质给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说“孩子这个山洞里有一些不同种类的草药采每一种都需要一些时间每一种也有它自身的价值。我会给你一段时间在这段时间里你可以采到一些草药。如果你是一个聪明的孩子你应该可以让采到的草药的总价值最大。”此题和原题的不同点每种草药可以无限制地疯狂采摘。输入第一行有两个整数t总共能用来采药的时间和m草药的数目。接下来m行每行包括两个整数分别表示采摘某一种草药的时间和价值。分析这是一道典型的完全背包问题 —— 每种草药可以采无限次时间是背包容量价值是草药价值。代码实现#include iostream #include algorithm #include cstring using namespace std; typedef long long LL; // 注意价值可能很大需要用long long const int N 1e4 10; // m最大1e4 const int M 1e7 10; // t最大1e7 int t, m; // t总时间m草药数 int time[N], val[N]; // time采药时间val草药价值 LL dp[M]; // 存储最大价值避免溢出 int main() { cin t m; for (int i 1; i m; i) { cin time[i] val[i]; } memset(dp, 0, sizeof dp); // 完全背包一维解法 for (int i 1; i m; i) { for (int j time[i]; j t; j) { dp[j] max(dp[j], dp[j - time[i]] val[i]); } } cout dp[t] endl; return 0; }示例输入70 3 71 100 69 1 1 2示例输出140解释总时间 70草药 3 的时间 1价值 2可以采 70 次草药 3总价值 70×2140这是最优解。四、01 背包与完全背包的对比总结为了方便大家记忆我们用表格总结两者的核心区别特征01 背包完全背包物品选择次数每个物品最多选 1 次每个物品可以选无限次二维状态转移方程dp[i][j] max(dp[i-1][j], dp[i-1][j-v[i]]w[i])dp[i][j] max(dp[i-1][j], dp[i][j-v[i]]w[i])一维容量枚举顺序从右到左V → v [i]从左到右v [i] → V核心代码差异j 从 V downto v [i]j 从 v [i] to V适用场景物品不可重复选择物品可重复选择关键口诀01 背包选或不选右到左填完全背包无限可选左到右填。五、常见误区与注意事项5.1 状态定义混淆很多初学者容易把状态定义为 “恰好装满容量j的最大价值”但默认情况是 “不超过容量j的最大价值”。这两种定义的初始化和结果判断完全不同一定要根据题目要求明确区分。5.2 容量枚举顺序错误这是最容易出错的地方01 背包用左到右枚举导致物品重复选择结果错误完全背包用右到左枚举导致物品无法重复选择退化为 01 背包。5.3 数据溢出问题当背包容量较大如 1e7或物品价值较高时int类型可能溢出需要用long long存储dp数组。5.4 初始化错误非恰好装满dp[j]初始化为 0恰好装满dp[0] 0其他dp[j] -∞。总结背包问题是动态规划的入门经典而 01 背包和完全背包则是背包问题的基石。掌握这两个模型不仅能解决直接相关的题目更能帮助我们理解动态规划的核心思想 ——“拆分问题、存储子问题解、避免重复计算”。接下来大家可以尝试解决多重背包、分组背包、多维背包等进阶问题将基础背包的思想迁移过去。相信只要吃透了 01 背包和完全背包后续的进阶内容都会迎刃而解。最后祝大家在算法的道路上越走越远攻克更多难题如果本文对你有帮助别忘了点赞、收藏、转发三连 有任何疑问或建议欢迎在评论区留言讨论