信息学奥赛一本通 1272：【例9.16】分组背包-北京尧图网络

【题目链接】ybt 1272【例9.16】分组背包【题目考点】1. 动态规划分组背包【解题思路】分组背包问题特点是每组中的物品最多可以取一件1. 状态定义集合放入背包的物品方案限制物品所在分组的区间背包大小属性价值条件最大统计量价值状态定义dp[i][j]: 在前i组物品中选择物品放入大小为j的背包能获得的最大价值。2. 状态转移方程记第i组物品有m个这m个物品的编号为i1,i2,…,im。第i物品的重量是w[i]价值是c[i]。集合在前i组物品中选择物品放入大小为j的背包的所有方案分割集合第i组物品如何放入背包如果不选择第i组物品那么在剩余i-1组中选择物品放入大小为j的背包。dp[i][j] dp[i-1][j]如果选择第i组物品中的第1个该物品下标为i1。那么需要在剩余i-1组中选择物品放入大小为j-w[i1]的背包。dp[i][j] dp[i-1][j-w[i1]]c[i1]如果选择第i组物品中的第2个该物品下标为i2。那么需要在剩余i-1组中选择物品放入大小为j-w[i2]的背包。dp[i][j] dp[i-1][j-w[i2]]c[i2]…如果选择第i组物品中的第m个该物品下标为im。那么需要在剩余i-1组中选择物品放入大小为j-w[im]的背包。dp[i][j] dp[i-1][j-w[im]]c[im]一般地如果选择第i组物品中的第k个该物品下标为x。那么需要在剩余i-1组中选择物品放入大小为j-w[x]的背包。dp[i][j] dp[i-1][j-w[x]]c[x]。遍历第i组物品求选择该组中每个物品后能得到的最大价值dp[i][j]。以上所有情况求最大值。3. 复杂度分析背包容量为V物品总数量为N分组数量为T。分组背包一般解法时间复杂度O ( V N ) O(VN)O(VN)空间复杂度O ( T V ) O(TV)O(TV)滚动数组优化后空间复杂度O ( V ) O(V)O(V)【题解代码】解法1分组背包一般解法#includebits/stdc.husingnamespacestd;#defineV205#defineN35#defineT15intdp[T][V],w[N],c[N];//dp[i][j]:在前i组物品中选择物品放入大小为j的背包能获得的最大价值。vectorintg[T];//g[i]:存储第i组物品的编号intmain(){intv,n,t,p;cinvnt;for(inti1;in;i){cinw[i]c[i]p;g[p].push_back(i);//第p组添加i}for(inti1;it;i)//遍历各组{for(intj0;jv;j){dp[i][j]dp[i-1][j];for(intk0;kg[i].size();k){intxg[i][k];if(w[x]j)dp[i][j]max(dp[i][j],dp[i-1][j-w[x]]c[x]);}}}coutdp[t][v];return0;}解法2分组背包滚动数组优化#includebits/stdc.husingnamespacestd;#defineV205#defineN35#defineT15intdp[V],w[N],c[N];//dp[i][j]:第1维被优化掉在前i组物品中选择物品放入大小为j的背包能获得的最大价值。vectorintg[T];//g[i]:存储第i组物品的编号intmain(){intv,n,t,p;cinvnt;for(inti1;in;i){cinw[i]c[i]p;g[p].push_back(i);//第p组添加i}for(inti1;it;i)//遍历各组{for(intjv;j0;--j){for(intk0;kg[i].size();k){intxg[i][k];if(jw[x])dp[j]max(dp[j],dp[j-w[x]]c[x]);}}}coutdp[v];return0;}

信息学奥赛一本通 1272：【例9.16】分组背包

相关推荐

pokemon 性能优化终极方案:模型量化与ONNX导出,让宝可梦识别速度飞起来

cookie、sessionStorage、localStorage 存储选型与安全边界详解

智能穿戴APP开发避坑指南：如何挑选靠谱服务商

更多资讯

TCP Tahoe与Reno拥塞控制仿真实验深度解析：原理、参数与避坑指南

王珊《数据库系统概论》第5版答案：关系代数与范式思维训练指南

DeepSeek-VL 上手指南：从装好环境到跑通多图像对话

res-downloader 完整使用指南：从打开软件到存下加密视频只要 5 分钟

AI正在撕掉嵌入式工具链的“价签”：从代码生成到调试的重构与实操

AI Agent 面试题 072：ReAct架构中Thought-Action-Observation循环是如何实现的？

今日更新

金融AI落地指南：从调研报告到技术选型与工程实践

大模型上下文成本与注意力优化技术深度解析——为何O(n²)平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测

基于GMM的语音识别系统原理与MATLAB实现详解

本周精选

金融AI落地指南：从调研报告到技术选型与工程实践

大模型上下文成本与注意力优化技术深度解析——为何O(n²)平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测

基于GMM的语音识别系统原理与MATLAB实现详解

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

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