algorithm - 资源共享/交易算法

Question

假设我们有 3 个人，Alice、Bob 和 Charlie。

假设他们每个人都有一种资源，Aplles、Bannanas 和 Coconuts。

他们每个人都有 3 个这种资源。

该算法的目标是进行 1-1 次交易，使每笔交易最终获得我们 3 种资源中的一种。这些交易的 list 就是我想要获得的。

理想情况下，我想知道如何解决这个问题。但我愿意满足于这种问题的名称，或者类似的问题，我可以研究并从中获得想法。

我正在处理的问题将有大约 600 个对象，大约 1000 个人，每个人都有随机数量/类型的起始资源，(假设有足够的资源来满足我们的最终结果)所以理想情况下任何解决方案提供这样的规模是可行的。但我会尽我所能，我只需要某种起点。

Answer 1

ElKamina 和 Tyler Durden 的回答不错，但他们似乎没有考虑到 Kuriso 喜欢进行 1-1 交易，人们可能有多种商品，以及多种商品单位。我有一个天真的解决方案。

我觉得原来的例子有点过于简单了，所以让我们再举一个:

  c1 c2 c3 c4
A 5  0  1  0
B 0  1  0  1
C 0  6  2  0

其中 A、B、C 是人，c1、c2、c3、c4 是商品。

首先，让我们计算一下理想的分布，这很容易做到:对于每种商品，将东西的总和除以人数，四舍五入，每个人都得到:

  c1 c2 c3 c4
A 1  2  1  0
B 1  2  1  0
C 1  2  1  0

现在让我们定义一个 WANT 函数，表示 X 需要多少东西 c 才能达到理想位置:WANT(X,c) = IDEAL(c) - Xc。

  c1  c2  c3  c4 sum
A -4  2   0   0  -2
B  1  1   1   0   3
C  1 -4  -1   0  -4

让我们列出一份按需求总和排序的人。让我们以最富有的人为例，他的需求最低，在本例中为 C，让我们尝试通过将他与最能提供他最想要的商品的人相匹配来满足他的需求。如果他们可以进行交易，那很好，如果不能，请继续，直到我们找到匹配(最终保证匹配)。在本例中，C 需要 c1；提供最多c1的是A，迭代商品，我们发现A需要c2，而C确实有剩余c2，所以他们交换了它们。更新他们在列表中的位置，或者如果他们不再需要，则将其删除。重复此操作，直到没有人想要为止。这不会产生适当的平等分配，但他们可以通过 1 对 1 交易达到平等。

这确实是一个天真的解决方案，其启发式认为最富有的人最有机会提供东西以换取他需要的商品。复杂性很高，但对于有序列表，它应该可以管理您指定的数字。