按比例解决分数背包问题
优先选择单位重量价值最高的物品
按比例解决分数背包问题 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 3 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。
背包问题设置
您有一些带价值和重量的物品，以及一个容量有限的背包。目标是在背包中装入尽可能大的总价值。🎒
分数型意味着可拆分
在分数型版本中，您可以只取物品的一部分，例如半袋粮食。正是这种自由让贪心算法在这里能够奏效。
单位重量价值
关键指标是每件物品的价值与重量之比率。比率越高，意味着在很小的空间中装入了越多价值。
ratio = value / weight按最佳比率排序
按单位重量价值从高到低sort物品。贪心策略就是不断选择当前可用的价值密度最高的物品。
items.sort(key=lambda i: i[0] / i[1], reverse=True)能装下就整件取走
遍历排序后的列表，如果物品完整放入剩余容量仍然合适，就取走整件物品，并将其完整价值加入总数。
if weight <= cap:
total += value
cap -= weight填补最后的空隙
当某件物品太大时，取其一部分分量，恰好填满剩余空间。此时背包已满，您就可以停止了。
total += value * (cap / weight)比率顺序为何有效
容量的每个单位都应当承载尽可能多的价值，因此必须优先放入密度最高的物品。换成密度更低的物品只会损失价值。
0/1 背包有所不同
如果物品不可分割，按比率使用贪心法就会失效。0/1 背包需要动态规划，而不是这种简单的排序。
运行时间
按比率排序的成本是 O(n log n)，装入循环则是线性的。对于典型的竞赛限制来说，这已经足够快了。
注意最后的部分物品
处理部分物品时，请使用浮点数或精确的有理数。过早截断可能会损失价值，导致答案错误。
应用场景
请设想装载货物、混合燃料或分配资源的场景。只要物品可以分割，比率贪心法就是您的工具。
快速检查
您正在解决分数背包问题，需要装满一个袋子。
回顾
请按单位重量价值对物品排序，在放得下时先取完整物品，然后取一部分来装满袋子。只有物品可以分割时，这种贪心法才是最优的。🚀
常见问题解答
「按比例解决分数背包问题」课时是免费的吗？
是的 — 「按比例解决分数背包问题」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。
「按比例解决分数背包问题」这节课中我会学到什么？
优先选择单位重量价值最高的物品 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Coding Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 3 节课，共 4 节。
「按比例解决分数背包问题」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Coding Interview Prep 课中编写并运行代码吗？
能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- 贪心思维
- 按最早结束时间选择活动
- 按比例解决分数背包问题
- 发现贪心法何时会失败