分数背包问题

分数背包问题也是用于解决背包问题的一种技术。在分数背包中，为了最大化利润，物品可以被分割。我们将物品分割的问题称为分数背包问题。

这个问题可以使用两种技术来解决

• 蛮力法：蛮力法尝试所有可能的解决方案，包含所有不同的分数，但这是一种耗时的方法。
• 贪心法：在贪心法中，我们计算利润/重量的比率，并据此选择物品。首先选择比率最高的物品。

解决这个问题主要有三种方法

• 第一种方法是根据最大利润选择物品。
• 第二种方法是根据最小重量选择物品。
• 第三种方法是计算利润/重量的比率。

考虑下面的示例

Objects:         1     2     3     4     5     6     7
Profit (P):         10     15     7     8     9     4
Weight(w):       1     3     5     4     1     3     2
W (Weight of the knapsack): 15
n (no of items): 7

第一种方法

第一种方法

总利润将等于 (15 + 10 + 9 + 8 + 5.25) = 47.25

第二种方法

第二种方法是根据最小重量选择物品。

在这种情况下，总利润将等于 (5 + 7 + 4 + 10 + 9 + 7 + 3) = 46

第三种方法

在第三种方法中，我们将计算利润/重量的比率。

物品：1 2 3 4 5 6 7

利润 (P)：5 10 15 7 8 9 4

重量(w)：1 3 5 4 1 3 2

在这种情况下，我们首先计算利润/重量的比率。

物品 1：5/1 = 5

物品 2：10/3 = 3.33

物品 3：15/5 = 3

物品 4：7/4 = 1.7

物品 5：8/1 = 8

物品 6：9/3 = 3

物品 7：4/2 = 2

P:w: 5 3.3 3 1.7 8 3 2

在这种方法中，我们将根据最大的利润/重量比选择物品。由于物品 5 的 P/W 最大，因此我们选择物品 5。

在物品 5 之后，物品 1 的利润/重量比最大，即 5。因此，我们选择物品 1，如下表所示

在物品 1 之后，物品 2 的利润/重量比最大，即 3.3。因此，我们选择利润/重量比为 3.3 的物品 2。

在物品 2 之后，物品 3 的利润/重量比最大，即 3。因此，我们选择利润/重量比为 3 的物品 3。

在物品 3 之后，物品 6 的利润/重量比最大，即 3。因此，我们选择利润/重量比为 3 的物品 6。

在物品 6 之后，物品 7 的利润/重量比最大，即 2。因此，我们选择利润/重量比为 2 的物品 7。

正如我们可以在上表中观察到的那样，剩余重量为零，这意味着背包已满。我们无法在背包中添加更多物品。因此，总利润将等于 (8 + 5 + 10 + 15 + 9 + 4)，即 51。

在第一种方法中，最大利润为 47.25。在第二种方法中，最大利润为 46。在第三种方法中，最大利润为 51。因此，我们可以说第三种方法，即最大利润/重量比是所有方法中最好的方法。

分数背包问题的 MCQ 练习

问题 1： 在分数背包问题中，哪个陈述是正确的？

1. 物品不能被分成更小的部分。
2. 整个物品可以包含在背包中。
3. 物品可以被分成更小的部分以最大化利润。
4. 这个问题可以使用动态规划来解决。

问题 2： 哪种技术对于解决分数背包问题最有效？

1. 动态规划
2. 分而治之
3. 蛮力法
4. 贪心法

问题 3： 假设物品的利润和重量如下：P = [5, 10, 15]，W = [1, 3, 5]，使用基于利润/重量比的贪心法，应该首先选择哪个物品？

1. 物品 1
2. 物品 2
3. 物品 3
4. 同时选择所有物品。

问题 4： 从提到的三种方式（最大利润方式、最小重量方式和最佳利润/重量比方式）来看，哪一种方式在给定的例子中赚的钱最多？

1. 最大利润方式
2. 最小重量方式
3. 最佳利润/重量比方式
4. 所有方式赚到的钱都一样。

问题 5： 在我们得到的例子中，在使用最佳利润/重量比选择物品后，您会最后选择哪个物品来填充背包？

1. 物品 1
2. 物品 5
3. 物品 6
4. 物品 7