交易资源的算法

Question

我正试图找到以下问题的最佳算法解决方案。这是一个现实世界的问题，但我将以抽象的方式呈现它。

有一个 1000 人的社区。每个用户都会获得一定数量的门票。有四种类型的门票(每一种对应不同的事件)。但也有人愿意做交易(比如我要一张A票，愿意放弃两张B票)。而且，有些人有多余的票，愿意白送(比如我送两张C票谁要)。假设我知道每个人愿意赠送/交易什么，我如何满足最多的人？

我试过谷歌搜索，但我不知道如何表达这个问题以避免得到与金融工具算法交易相关的结果。

谢谢。

Answer 1

鉴于它具有多个维度，它很可能是一个 NP 完全问题。它类似于多维背包问题。

因此，我建议尝试回溯方法。

从参与交易的每个人开始。

对导致赤字最多的人进行降序排序(在这里您可以根据每张票的缺口对每种票类型造成的赤字进行加权)。

然后以回溯的方式，将造成下一个赤字最高的人踢出交易。

重复，直到你在任何一张票中都没有更多的赤字(记录为可能的答案)，或者你已经把所有人都踢出去了。

当发生这种情况时，回溯 1 步并继续(如果您已经尝试踢出最高的赤字，则踢掉下一个造成最高赤字的人)。

重复直到结束或时间用完。从您找到的可能答案中获得最佳答案。

如果问题太难，它可能会用完时间。否则，该算法应该会给你一个合理的答案(可能接近最优)。

此方法的效果如何取决于人们的慷慨/贪婪程度、人数以及您的计算机的速度。