打包算法......有点
给定一个项目数组，每个项目都有一个值和成本，确定以最小成本达到最小值所需的项目的最佳算法是什么？ 例如：
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 code> 是一个更便宜的选项，它达到最小值）。
Given an array of items, each of which has a value and cost, what's the best algorithm determine the items required to reach a minimum value at the minimum cost? eg:
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
Note that the overall value:cost ratio at the end is irrelevant (A + A would give you the best value for money, but A + B + B is a cheaper option which hits the minimum value).
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
这就是背包问题。 （也就是说，该问题的决策版本与背包问题的决策版本相同，尽管背包问题的优化版本通常有不同的表述。）它是 NP 难的（这意味着没有已知的算法是“大小”中的多项式——位数——输入中）。 但是，如果您的数字很小（例如，输入中的最大“值”；成本并不重要），那么有一个简单的动态规划解决方案。
令 best[v] 为获得（精确）v 值的最小成本。然后您可以通过（将所有 best[v] 初始化为无穷大）计算所有 v 的值 best[]：
然后查看 best[ v] 为您想要的最小值加上最大值； 其中最小的一个将为您提供成本。
如果您想要实际的项目（而不仅仅是最低成本），您可以维护一些额外的数据，或者只是查看 best[] 数组并从中推断。
This is the knapsack problem. (That is, the decision version of this problem is the same as the decision version of the knapsack problem, although the optimization version of the knapsack problem is usually stated differently.) It is NP-hard (which means no algorithm is known that is polynomial in the "size" -- number of bits -- in the input). But if your numbers are small (the largest "value" in the input, say; the costs don't matter), then there is a simple dynamic programming solution.
Let best[v] be the minimum cost to get a value of (exactly) v. Then you can calculate the values best[] for all v, by (initializing all best[v] to infinity and):
Then look at best[v] for values upto the minimum you want plus the largest value; the smallest of those will give you the cost.
If you want the actual items (and not just the minimum cost), you can either maintain some extra data, or just look through the array of best[]s and infer from it.
这个问题称为整数线性规划。 这是 NP 困难的。
然而，对于像您的示例这样的小问题，快速编写几行代码来简单地暴力破解所有购买选择的低组合是微不足道的。
NP 困难并不意味着不可能，甚至昂贵，它意味着您的问题在解决大规模问题时会变得非常慢。 在您只有三个项目的情况下，您可以在短短几微秒内解决这个问题。
对于一般最好的算法是什么的确切问题..有完整的教科书。 一个好的开始是好的旧维基百科。
This problem is known as integer linear programming. It's NP-hard.
However, for small problems like your example, it's trivial to make a quick few lines of code to simply brute force all the low combinations of purchase choices.
NP-harddoesn't mean impossible or even expensive, it means your problem becomes rapidly slower to solve with larger scale problems. In your case with just three items, you can solve this in mere microseconds.
For the exact question of what's the best algorithm in general.. there are entire textbooks on it. A good start is good old Wikipedia.
编辑由于事实不正确，该答案已被编辑。 遵循本文中的建议只会给您带来伤害。
这实际上不是背包问题，因为它假设您打包的物品不能超过某个容器中的空间。 在您的情况下，您希望找到最便宜的组合来填充空间，并考虑到可能发生溢出的事实。
我的解决方案（我不知道是最佳的，但应该非常接近）是计算每个项目的成本效益比，找到成本效益最高的项目，并用该项目填充结构，直到没有“没有空间再容纳一件物品。 然后我会测试是否存在与任何其他可用物品的组合，可以以低于最便宜物品之一的成本填充可用插槽，然后如果存在这样的解决方案，则使用该组合，否则再使用一个最便宜的商品。
Amenddum 这实际上也可能是 NP 完全的，但我还不确定。 无论如何，出于所有实际目的，这种变化应该比简单的解决方案快得多。
Edit This answer is redacted on account of being factually incorrect. Following the advice in this will only cause you harm.
This is not actually the knapsack problem, because it assumes that you cannot pack more items than there is space for in some container. In you case you want to find the cheapest combination that will fill up the space, allowing for the fact that overflow may occur.
My solution, which I don't know is the optimal but it should be pretty close, would be to compute for each item the cost benefit ratio, find the item with the highest cost benefit and fill the structure with this item until there isn't space for one more item. Then I would test to see if there was a combination with any of the other available items that could fill the available slot for less that the cost of one of the cheapest items and then if such a solution exist, use that combination otherwise use one more of the cheapest items.
Amenddum This may actually also be NP-complete, but I am not sure yet. Anyway for all practical purposes this variation should be much faster than the naive solution.