分数背包：为什么是价值/重量？

Question

在分数背包问题中，

1。准备第三个数组，每个权重数组的值，将每个项目的权重除以其对应的值

2。根据物品的重量价值按降序排列

步骤 1 和 2 背后的原因？

Answer 1

因为用具有最高价值/重量比的物质填充所有可能的体积更有利可图。因此，请用完所有给定数量的具有最佳价值/重量比的物品，然后使用第二个，依此类推。

想一想 - 如果您认为可以用不太有价值的物品填充某些部分（同时可以使用更有价值的物品） - 将其更改为更有价值的物品，您将获得一些额外的钱

Answer 2

在分数背包中，您可以在背包（答案）中添加部分/部分物品，以最大化包中物品的总价值。由于我们的目标是最大化背包中的总价值，因此我们应该放置物品，使得放置的重量值较高并且占用尽可能少的空间，以便可以向背包添加更多物品。因此，需要计算每个值的权重。背包的容量不是无限的，因此我们需要单位重量的价值来最佳地利用空间。

例如，如果我们的重量 ={10,20,30,} 和值 {60,100,120} 并且袋子最多可以容纳 50 个，那么如果不划分该项目，那么我们只能拥有 1 个 20 的项目和 1 个 30 的项目。所以总价值将为 220。

但是根据分数背包，我们将值除以重量并得到数组 {6,5,4} 。排序（已经排序）。现在item的顺序变成了i1,i2,i3

Take all 10 kg of i1=6*10
Take all 20kg of i2= 5*20
Take the remaining 20kg from  i3= 4*((2/3)*30)

总价值= 60+100+80= 240

因此，我们需要单位重量的价值。

参考链接：https://www.geeksforgeeks.org/fractional-knapsack-problem/

Answer 3

这与基础数学有关。让我们取一个常数，它有分子和分母。

在这种情况下：

常数：价值/重量比。
分子：值
分母：重量

由于常数和分子有直接关系，常数越大，分子也越大。同时，当常数越大时，分母越小，因为它们具有间接关系。

因此，当我们按降序排列比率时，我们试图对最大价值和相对较小重量的条目进行排序，并将它们按顺序放入给定容量的包中。

Answer 4

在分数背包问题中这样做的两个主要原因：

• 按价值重量比对物品进行排序可以采用贪婪方法，您可以考虑按价值重量比的降序将物品添加到背包中。这意味着您会优先考虑那些以最轻的重量为您带来最大价值的物品。
• 您可以添加部分物品，因此从最有价值的物品开始，以在保持重量限制的同时最大化总价值非常重要。