1

给定一个项目数组，每个项目都有一个value和cost，确定以最小成本达到最小值所需的项目的最佳算法是什么？例如：

Item: Value -> Cost
-------------------
A     20   -> 11
B     7    -> 5
C     1    -> 2

MinValue = 30
naive solution: A + B + C + C + C. Value: 30, Cost 22
best option: A + B + B.            Value: 34, Cost 21

请注意，最后的总体价值：成本比是无关紧要的（A + A会给你最好的物有所值，但A + B + B它是一个更便宜的选择，它达到了最小值）。

4

3 回答 3

8

这就是背包问题。（也就是说，这个问题的决策版本与背包问题的决策版本相同，尽管背包问题的优化版本通常有不同的表述。）它是 NP-hard（这意味着没有已知的算法是“大小”中的多项式——位数——在输入中）。但是，如果您的数字很小（例如输入中的最大“值”；成本无关紧要），那么有一个简单的动态规划解决方案。

让 best[v] 是获得（精确）v 值的最小成本。然后您可以通过（将所有 best[v] 初始化为无穷大和）计算所有 v 的值 best[]：

best[0] = 0
best[v] = min_(items i){cost[i] + best[v-value[i]]}

然后查看 best[v] 的值，直到您想要的最小值加上最大值；其中最小的会给你成本。

如果您想要实际项目（而不仅仅是最低成本），您可以维护一些额外的数据，或者只是查看 best[] 数组并从中推断。

于 2008-11-27T01:36:34.710 回答
0

这个问题被称为整数线性规划。这是NP难的。但是，对于像您的示例这样的小问题，快速编写几行代码来简单地强制所有购买选择的低组合是微不足道的。

NP-hard 并不意味着不可能甚至昂贵，它意味着您的问题在解决更大规模的问题时会变得迅速变慢。在您只有三个项目的情况下，您可以在几微秒内解决这个问题。

对于一般来说最好的算法是什么的确切问题......有整本教科书。一个好的开始是好的旧维基百科。

于 2009-05-02T13:34:33.813 回答
-1

编辑由于事实不正确，此答案已被编辑。遵循此处的建议只会对您造成伤害。

这实际上不是背包问题，因为它假定您装的物品不能超过某个容器的空间。在你的情况下，你想找到最便宜的组合来填满空间，考虑到可能发生溢出的事实。

我的解决方案，我不知道是最优的，但应该非常接近，将计算每个项目的成本效益比，找到具有最高成本效益的项目并用这个项目填充结构，直到没有' t 空间再放一项。然后我会测试看看是否有任何其他可用项目的组合可以以低于最便宜项目之一的成本填充可用槽，然后如果存在这样的解决方案，请使用该组合，否则再使用一个最便宜的物品。

修正这实际上也可能是 NP 完全的，但我还不确定。无论如何，出于所有实际目的，这种变化应该比天真的解决方案快得多。

于 2009-05-02T13:22:40.860 回答