首页/新闻资讯/正文详情

贪心算法经典例题:背包问题(C++ 代码逐行讲解)

发布时间:2026/9/26 3:30:17 来源:云帆数科 栏目:资讯中心
贪心算法经典例题:背包问题(C++ 代码逐行讲解)
1. 题目背景这段代码解决的是经典的部分背包问题Fractional Knapsack给定x件物品每件物品有质量m和价值v背包容量为y要求在不超过背包容量的前提下使装入背包的物品总价值最大。与 0-1 背包不同这里的物品可以分割比如大米、面粉、金砂所以我们可以按比例取走一部分这就让贪心策略成为可能。2. 核心思路贪心策略贪心的关键在于性价比——单位质量的价值v / m。我们总是优先选择「单位价值最高」的物品能全装就全装装不下就按剩余容量取一部分直到背包装满。这个策略之所以正确是因为物品可分割只要每次都拿当前性价比最高的最终一定能得到全局最优解。3. 代码逐行讲解3.1 结构体与全局数组structValue{floatm;// 物品质量floatv;// 物品价值};Value values[105];// 最多 105 件物品定义结构体Value保存每件物品的质量m和价值v并用全局数组values存储所有物品。3.2 排序比较函数boolcmp(Value a,Value b){returna.vb.v;// 按单位价值降序排列}这是sort的比较函数。注意在main中已经提前把v变成了「单位价值」v / m所以这里直接按v降序排序即可性价比高的物品排在前面。3.3 主函数输入与预处理intx,y;cinxy;// x 件物品背包容量 yfor(inti0;ix;i){cinvalues[i].m;// 输入质量cinvalues[i].v;// 输入价值}for(inti0;ix;i){values[i].v/values[i].m;// 计算单位价值 v/m}先读入物品数量和背包容量再读入每件物品的质量与价值。随后把每件物品的v原地更新为单位价值v / m为排序做准备。3.4 排序sort(values,valuesx,cmp);按单位价值从高到低排序性价比最高的物品排在最前面。3.5 贪心装入floatsum0;for(inti0;ix;i){if(values[i].my){// 当前物品能整件装下sumvalues[i].m*values[i].v;// 全装价值 质量 × 单位价值y-values[i].m;// 剩余容量减少}else{// 装不下整件只能装一部分sumy*values[i].v;// 用剩余容量 y 乘以单位价值break;// 背包已满结束}}printf(%.2f,sum);// 保留两位小数输出最大总价值这是核心循环若当前物品质量m不超过剩余容量y就整件装入累加价值m × v此时v是单位价值并扣减剩余容量若装不下整件就按剩余容量取一部分累加y × v然后break结束——因为背包已经满了后面的物品即使性价比再高也装不进去了。最后用printf(%.2f, sum)保留两位小数输出结果。4. 复杂度分析时间复杂度排序为O(x log x)贪心装入为O(x)整体O(x log x)。空间复杂度O(x)用于存储物品数组。5. 易错点提醒单位价值要提前算好排序前必须把v更新为v / m否则排序依据错误。浮点精度m、v用float计算v / m时注意类型避免整数除法丢失小数。break不能漏当装不下整件、只能取一部分时背包已满必须跳出循环否则会继续错误累加。输出格式题目要求保留两位小数用printf(%.2f, sum)或cout fixed setprecision(2)。6. 总结这段代码是贪心算法处理部分背包问题的经典实现先算性价比单位价值按性价比降序排序再依次装入装不下就取一部分。理解「物品可分割」这一前提是理解整个贪心策略正确性的关键。

相关推荐

【共创稿事节】鸿蒙文搜图 · 回忆胶囊:用一句话搜出照片,封存成带倒计时的时间胶囊,到期才能开启
【共创稿事节】鸿蒙文搜图 · 回忆胶囊:用一句话搜出照片,封存成带倒计时的时间胶囊,到期才能开启

【共创稿事节】鸿蒙文搜图 回忆胶囊:用一句话搜出照片,封存成带倒计时的时间胶囊,到期才能开启 文搜图第一篇把「找到」做完了:一句话进、相似度排序的图片网格出。但「找到」之后呢?翻出来就看完关掉,和没… · 2026/9/26 3:30:11

脉冲同步法:跨时钟域单周期脉冲传输的可靠实现与工程实践
脉冲同步法:跨时钟域单周期脉冲传输的可靠实现与工程实践

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/26 3:30:05

Cursor Windows 环境与账号追踪机制分析:TaoToken 统一 Key 接入配置与验证
Cursor Windows 环境与账号追踪机制分析:TaoToken 统一 Key 接入配置与验证

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/26 3:30:05

无密码卸载ThreatbookAgent:注册表深度清理实战指南
无密码卸载ThreatbookAgent:注册表深度清理实战指南

1. 项目概述:为什么“无密码卸载ThreatbookAgent”是个真实存在的刚需场景ThreatbookAgent 是国内某主流威胁情报与终端安全平台部署的轻量级探针客户端,常用于企业内网资产测绘、行为日志采集和EDR联动响应。它不是传统意义上的杀毒软件,而更… · 2026/9/26 6:25:03

多Agent开发实战:拆分与复制,让每个Agent专注一件事
多Agent开发实战:拆分与复制,让每个Agent专注一件事

做Agent开发这两年,我最大的体会就是:一个Agent什么都能干,往往最后什么都干不好。你把资料搜集、数据清洗、图表生成、报告撰写全塞进一个Agent里,提示词写到五千字,工具配了七八个,结果它要么在中间步骤跑… · 2026/9/26 6:25:03

SpringBoot+Vue社区维修平台:接单并发与状态同步实战
SpringBoot+Vue社区维修平台:接单并发与状态同步实战

简介:本资源为基于SpringBoot与Vue的社区维修平台毕业设计完整项目,面向计算机相关专业需要完成课程设计、毕业设计或期末大作业的学生。项目采用前后端分离架构,后端以SpringBoot(或SSM)搭建,数据库使用My… · 2026/9/26 6:25:03

Agent影分身术:从fork到多Agent编排的并行加速实践
Agent影分身术:从fork到多Agent编排的并行加速实践

最近在搞Agent落地项目时遇到一个特别拧巴的需求:一个Agent不够用。倒不是说模型能力不行,而是任务量真的顶不住。我这边同时要开三个活儿——一个写项目周报、一个做数据异常分析、一个给刚上线的功能写排障FAQ——如果让Agent一个接一个串行处理&#… · 2026/9/26 6:25:03

水声换能器设计速查:参数、指向性、匹配与工程实战
水声换能器设计速查:参数、指向性、匹配与工程实战

1. 换能器在水声工程里的位置:为什么它是绕不开的核心干水声这行的人,心里都清楚一件事:整个系统能不能用、好不好用,一半的命脉压在换能器身上。发射换能器负责把电信号变成声波,接收换能器负责把声波变回电信号&… · 2026/9/26 6:25:03

低空经济项目文档实战:报告架构、政策解读与BP设计方法论
低空经济项目文档实战:报告架构、政策解读与BP设计方法论

低空经济大概是这两年最典型的“名词先热、产业后热”赛道。身边所有人都在讨论无人机物流、飞行汽车、城市空中交通,可真到要落地一份行业报告、政策解读或商业计划书时,很多人会发现网上能搜到的资料要么是碎片化新闻,要么是互相打架的数据… · 2026/9/26 6:24:57

数据库课后习题答案别硬背:当测试用例集刷,效率翻倍
数据库课后习题答案别硬背:当测试用例集刷,效率翻倍

简介:万常选版《数据库原理与设计》课后习题答案资源,覆盖第2至6章及第9章,适合正在学习关系模型、数据库建模、关系数据理论与模式求精的本科生、自学者作为复习与自测材料。压缩包共7个文件,含3个doc参考答案、2个sql示例脚本、… · 2026/9/26 0:00:21

OpenClaw 替代品?Hermes Agent 踩坑实录:macOS 飞书接入 TaoToken 配置
OpenClaw 替代品?Hermes Agent 踩坑实录:macOS 飞书接入 TaoToken 配置

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/26 0:00:40

向下兼容与向上兼容:接口设计中的兼容性策略与工程实践
向下兼容与向上兼容:接口设计中的兼容性策略与工程实践

一次版本升级事故,是很多团队绕不过去的坎。线上环境里,服务端明明已经上线了新版接口,老的移动端还在照着旧文档传参数。请求一到网关,校验直接拒绝,用户操作失败,客服群炸了锅,开发群里开始互… · 2026/9/26 0:00:46

了解更多?预约专属演示

我们的顾问将为您一对一讲解产品与方案

企业微信二维码