我正在尝试找到以下问题的最佳算法解决方案。这是一个现实世界的问题，但我将以抽象的方式呈现它。
有一个1000人的社区。为每个用户提供一定数量的票。有四种类型的门票（每种类型对应不同的事件）。但是，有些人愿意进行交易（例如，我想要一张 A 票，而愿意放弃两张 B 票）。而且，有些人有多余的票，他们愿意白送（例如，我会给想要的人两张C票）。假设我知道每个人愿意放弃/交易什么，我如何满足最多的人？
我尝试了谷歌搜索，但我不知道如何描述这个问题以避免获得与金融工具算法交易相关的结果。
谢谢。
问问题
440 次
2 回答
0
鉴于它具有多个维度，它很可能是一个 NP 完全问题。它与多维背包问题有相似之处。
因此，我建议尝试回溯方法。
从参与交易的每个人开始。
对造成赤字最多的人进行降序排序（在这里，您可以通过每张票中的亏空来衡量每种票种造成的赤字）。
然后以一种回溯的方式，将导致第二高赤字的人踢出交易。
重复直到你在任何一张票上都没有更多的赤字（记录尽可能的答案），或者你把每个人都踢了出去。
发生这种情况时，回溯 1 步并继续（如果您已经尝试踢出最高赤字，则踢下一个最高赤字导致的人）。
重复直到结束，否则你的时间用完了。从您找到的可能答案中找出最佳答案。
如果问题太难，它可能会用完时间。否则，这个算法应该给你一个合理的答案（也许接近最优）。
这种方法的效果取决于人们有多慷慨/贪婪，有多少人，以及你的计算机有多快。
于 2012-08-19T03:08:25.300 回答
0
寻找二分最小权重匹配问题。这个想法是仅使用顶点 1 .. k 找到从 i 到 j 的最短距离。
于 2012-08-19T07:43:09.980 回答