动态规划解决背包问题：洛谷P1164小A点菜详解-北京尧图网络

1. 问题背景与需求分析洛谷P1164小A点菜是一道经典的动态规划入门题目题目描述如下小A去餐厅点菜餐厅提供N道不同价格的菜品需要计算出恰好花完M元的点菜方案数。这道题的核心在于理解恰好花完这个条件以及如何用动态规划来高效计算方案数。在实际解题过程中很多初学者容易陷入两个误区一是试图用暴力枚举所有可能的组合这在N较大时会导致指数级的时间复杂度二是对状态转移方程的理解不够透彻导致无法正确处理边界条件。而二维DP解法能够清晰地展现状态转移的过程特别适合作为动态规划的学习案例。提示这道题的难点不在于编码实现而在于理解为什么二维DP是解决此类恰好装满背包问题的最佳选择。2. 二维DP解法核心思路2.1 状态定义与初始化我们定义一个二维数组dp[i][j]表示考虑前i道菜品时恰好花费j元的方案数。其中i的范围是0到N菜品编号从1开始j的范围是0到M目标金额初始化时dp[0][0] 1表示0道菜品花费0元有1种方案什么都不选其他dp[0][j] 0表示没有菜品可选时无法花费任何金额vectorvectorint dp(N1, vectorint(M1, 0)); dp[0][0] 1;2.2 状态转移方程推导对于每道菜品我们有两种选择选或者不选。这引出了状态转移的两种情况不选第i道菜方案数继承自dp[i-1][j]选第i道菜只有当j price[i]时方案数加上dp[i-1][j-price[i]]因此状态转移方程为if(j price[i]) { dp[i][j] dp[i-1][j] dp[i-1][j-price[i]]; } else { dp[i][j] dp[i-1][j]; }2.3 完整代码实现#include iostream #include vector using namespace std; int main() { int N, M; cin N M; vectorint price(N1); for(int i1; iN; i) { cin price[i]; } vectorvectorint dp(N1, vectorint(M1, 0)); dp[0][0] 1; for(int i1; iN; i) { for(int j0; jM; j) { if(j price[i]) { dp[i][j] dp[i-1][j] dp[i-1][j-price[i]]; } else { dp[i][j] dp[i-1][j]; } } } cout dp[N][M] endl; return 0; }3. 算法优化与空间复杂度分析3.1 空间优化到一维观察状态转移方程可以发现dp[i][j]只依赖于dp[i-1][...]因此可以优化为一维数组vectorint dp(M1, 0); dp[0] 1; for(int i1; iN; i) { for(int jM; jprice[i]; j--) { // 注意这里是倒序遍历 dp[j] dp[j-price[i]]; } }注意内层循环必须倒序遍历否则会重复计算同一道菜的选择3.2 时间复杂度对比二维DPO(NM)时间O(NM)空间一维DPO(N*M)时间O(M)空间虽然时间复杂度相同但空间复杂度从O(N*M)降到了O(M)这在M较大时能显著减少内存使用。4. 常见错误与调试技巧4.1 初始化错误常见错误1忘记初始化dp[0][0]1表现输出总是0原因没有考虑什么都不选也是一种方案常见错误2错误地初始化所有dp[0][j]1表现输出结果偏大原因错误认为不选任何菜品时可以有任意金额的方案4.2 边界条件处理常见错误3内层循环从j1开始for(int j1; jM; j) // 错误会漏掉j0的情况表现当有价格为0的菜品时结果错误修正应该从j0开始4.3 一维DP的实现陷阱常见错误4一维DP中使用正序遍历for(int jprice[i]; jM; j) // 错误会导致重复计算表现结果比实际大很多原因正序遍历会多次累加同一道菜的选择5. 同类问题扩展与变种5.1 变化问题1每种菜品有无限个如果每道菜可以点多次只需将一维DP的内层循环改为正序for(int jprice[i]; jM; j) { dp[j] dp[j-price[i]]; }5.2 变化问题2输出所有具体方案如果需要输出所有具体的点菜方案可以用回溯法void backtrack(int i, int remaining, vectorint path) { if(remaining 0) { // 输出path中的方案 return; } if(i 0 || remaining 0) return; // 选第i道菜 path.push_back(price[i]); backtrack(i-1, remaining-price[i], path); path.pop_back(); // 不选第i道菜 backtrack(i-1, remaining, path); }5.3 变化问题3考虑菜品数量限制如果每道菜最多点k次状态需要增加一维表示已选次数dp[i][j][l] // l表示第i道菜已经选了l次6. 实际应用场景分析这类恰好装满背包的问题在实际中有广泛应用财务规划给定一组投资选项和目标金额计算达到目标的投资组合方案数库存管理用不同规格的包装组合来满足精确的订单需求游戏开发计算玩家用不同面额游戏币兑换特定金额的兑换方式餐饮系统正如本题计算满足特定预算的点餐组合在实际编码面试中这类问题也经常出现例如LeetCode 518. Coin Change 2LeetCode 377. Combination Sum IV背包问题的各种变种理解二维DP解法不仅能解决这道特定题目更能为处理更复杂的动态规划问题打下坚实基础。我建议初学者在理解这个解法后可以尝试用同样的思路解决上述LeetCode题目体会其中的异同点。

动态规划解决背包问题：洛谷P1164小A点菜详解

相关推荐

OpenRig：用铝型材和3D打印打造模块化桌面设备支架

VoiceStudio深度评测：AI语音合成与音色克隆的完整实操指南

SAP Fiori内容发布日志解析与故障排查指南

更多资讯

Kornia 精度修复：`ConvQuadInterp3d` / `conv_quad_interp3d` 的 float16 梯度溢出（NaN）问题与 float32 提升方案

Kornia 增强 API 文档修正与 ColorJitter 固定 `order`：打造 torch.compile fullgraph 安全的确定性颜色增强

Kornia normalize_quaternion float16 数值修复解析：eps 下限与除法保护机制的实现原理

Kornia nms2d 支持非方形 kernel_size：一次 NMS 邻域核构造修复的源码级解析

Kornia 颜色空间转换的 TorchScript 兼容性修复：从 PEP 604 联合类型到 `Optional[torch.Tensor]`

PaperOrchestra Outline Agent工作原理：1次LLM调用如何生成驱动全局的outline.json

今日更新

PLFM_RADAR：从被动告警到主动感知的微服务健康监控系统

SPI隔离设计实战：MAX14431BAEE+与STM32F407工业级应用

数字隔离器如何根治SPI通信地环路干扰：MAX14431与TM4C129实战

本周精选

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？