10.4.1　分数背包问题

我们常说的背包问题主要分为以下几种：分数背包、0-1背包、完全背包、多重背包、分布背包等。

其中分数背包，用贪心算法求可装入最大价值总物品，当装入物品体积不够时，可通过切割其最后一个物品来实现。对于装入背包物品的最大价值的判断，可以优先放入单位体积价值大的物品，也可以优先放入价格高的物品，或优先放入体积最小（或最大）的物品。由此，用贪心算法得到的背包最优解只能是局部的，不一定是全局最优解。

表10.1所示的为可以挑选装入背包的物品名称、体积、价格，背包体积为12，用贪心算法求解，该背包可以装入的最大价值的物品。这里优先放入单位体积价值最大的物品。