特殊分配问题的有效解决方案
给定：
- 一组物品，每个物品放入给定容器类型时都会产生成本。
-一组容器类型，每种类型都有多个可用容器。
示例：
数量*容器类型：5 * A、3 * B、2 * C
物品（成本）：
3 * X (A=2, B=3, C=1)
2 * Y (A=5, B= 2, C=2)
1 * Z (A=3, B=3, C=1)
问题：
找到将物品放入容器中的最佳位置，以使成本最小。 为简单起见，仅将物品放入单一类型的容器中。
我尝试了匈牙利方法来解决这个问题，但是由于运行时间为 O(n³)，对于大型问题（例如 100000 个项目）来说这是相当令人望而却步的。
我当前的解决方案是一种贪婪方法，即按成本 (asc) 对项目容器组合进行排序，并在 O(n log n) 中分配剩余足够数量的第一个容器。
有更好的解决方案吗？
Given:
-A set of items that each have costs for being placed into a given container type.
-A set of container types that each have a number of available containers.
Example:
Amount*Container-Type : 5 * A, 3 * B, 2 * C
Items(Costs) :
3 * X (A=2, B=3, C=1)
2 * Y (A=5, B=2, C=2)
1 * Z (A=3, B=3, C=1)
Problem:
Find the best placement of the items into the containers so that the costs are minimal. For simplicity, only place an item into a single type of container.
I tried the hungarian method to solve the problem, but with a runtime of O(n³), it's quite prohibitive for large problems (e.g., 100000 items).
My current solution is a greedy approach, that just orders the item-container combinations by costs (asc) and assigns the first container with a sufficient amount left in O(n log n).
Is there a better solution?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
这个问题是背包问题的变体，从维基百科页面开始并从那里继续阅读。
众所周知，贪心算法是一个相当好的近似算法，因此您可能已经足够好了。
This problem is a variant of the Knapsack problem, start at the Wikipedia page and read on from there.
The greedy algorithm is known to be a reasonably good appoximation, so you are probably good enough.
考虑到基因组很容易生成、突变和杂交，我自然会选择遗传方法。 但可能存在最优的非组合解决方案。
Nahively I would go for a genetic aproach, given that genomes are easy to generate, mutate and cross-breed. but there may be an optimal non-combinatory solution.
如果我正确理解你的问题，你只需要一些数学：
http://en.wikipedia .org/wiki/Optimization_%28mathematics%29
If I understood your problem right, you only need some maths:
http://en.wikipedia.org/wiki/Optimization_%28mathematics%29
您是否尝试过将分配问题编写为线性规划 并使用
Have you tried writing the assignment problem as a linear program and solving it using the simplex algorithm?