分数背包问题：为何采用价值重量比？核心步骤原理探究

咱们先把第一个疑问拆解明白：为什么要构建价值重量比数组？

分数背包的核心是允许我们拿走物品的一部分，而非只能拿完整的一件。这时候，单纯看物品的总价值或者总重量都没意义——比如你有个10kg、总价值100块的箱子，和一个1kg、总价值20块的小包裹，总价值前者更高，但前者每kg只值10块，后者每kg值20块，显然优先拿小包裹能让背包里的价值更高。

这里要先纠正个小细节：咱们要算的是价值/重量的比值（你说的“重量除以价值”是笔误啦），这个比值本质就是每个物品单位重量能带来的价值。有了这个比值，我们就能直接量化每个物品“每克值多少钱”，这才是分数背包里判断物品优先级的核心指标——毕竟我们要在有限的背包容量里，塞下尽可能多的价值，单位重量价值越高，性价比就越高。

接下来聊第二个问题：为什么要按价值重量比降序排序？

这其实是贪心算法的核心逻辑——每次选当前最优的选项，最终就能得到全局最优解。在分数背包里，当前最优的选择就是单位重量价值最高的物品：我们先把这个物品尽可能多的塞进背包（能拿满就拿满，拿不满就拿剩下容量对应的部分），然后再处理下一个单位重量价值次高的物品，以此类推，直到背包被填满。

如果不做降序排序，随便选物品的话，很可能会先拿了低性价比的物品，占用了背包容量，导致后面更高性价比的物品塞不进去，最终总价值就不是最大的。比如背包容量是5kg，刚才的例子里，如果你先拿了那个10kg的箱子（只能拿5kg，价值50块），总价值就是50；但如果先拿1kg的小包裹（拿5份，总价值100块），显然后者收益更高——这就是降序排序后优先选高性价比物品的意义。

内容的提问来源于stack exchange，提问作者Monika Bhajipale