资源交易算法

Question

我正在尝试找到以下问题的最佳算法解决方案。这是一个真实的问题，但我将以一种抽象的方式来介绍它。

有一个1000人的社区。为每个用户提供设定数量的票证。门票有四种类型(每种门票对应一个不同的事件)。然而，有些人愿意进行交易(例如，我想要一张A票，但愿意放弃两张B票)。此外，有些人有多余的票，他们愿意免费赠送(例如，我会将两张C票赠送给任何想要它们的人)。假设我知道每个人愿意赠送/交换什么，我如何满足最多的人？

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

谢谢。

Answer 1

考虑到它有多个维度，它很可能是一个NP-完全问题。它与多维背包问题有相似之处。

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

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

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

然后以一种回溯的方式，将导致下一个最高赤字的人踢出该行业。

重复这一过程，直到你在任何票证中都不再有赤字(记录为可能的答案)，或者你已经把每个人都踢出去了。

当这种情况发生时，回溯1步并继续(如果你已经尝试踢最高赤字，踢下一个引起赤字最高的人)。

重复直到结束，否则你的时间会用完。从你找到的可能答案中找出最佳答案。

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

这种方法的效果取决于人们有多慷慨/贪婪，有多少人，以及你的计算机有多快。

Answer 2

寻找二部最小权值匹配问题。其思想是使用顶点1来找到从i到j的最短距离。仅限K。