资源共享/交易算法

Question

假设我们有3个人，分别是爱丽丝、鲍勃和查莉。

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

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

算法的目标是进行一对一的交易，这样每一笔交易最终都会得到我们3个资源中的1个。我想要的是一份这些交易的清单。

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

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

Answer 1

ElKamina和Tyler Durden的答案是不错的，但他们似乎没有考虑到库里索希望进行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，所以他们交换它们。更新他们在列表中的位置，如果他们不再有任何需要，则将其删除。重复这个过程，直到没有人想要为止。这不会产生适当的平等分配，但只要他们通过一对一的交易就能达到平等。

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

Answer 2

假设您有种类为1，...，xn的x1资源总数为n。

假设你有k个人，他们每个人都有(或需要分别以y1，y2，...，yk资源结束)。

现在，选择一个人i，并为他分配最流行的资源。一旦分配完成，则递减相应的xj s(即，如果资源j被分配给i，则递减xj)。

不断重复，直到分配完所有资源。

这是最均匀地分配东西的方法。它假设你关心的不是交易顺序，而是最终结果本身。

Answer 3

为了重申这一点，我们假设你有一组这样的列表：

{ 1，1，1}

{ 2，2，2}

{ 3，3，3}

并且您想要交换来自不同集合的元素，直到您拥有这样的集合：

{ 1，2，3}

{ 1，2，3}

{ 1，2，3}

现在，你可能会注意到，如果我们把这些列表看作一个矩阵，那么一个矩阵就是另一个矩阵的逆。您可以通过在1-2-3对角线上交换来执行此反转。

因此，列表1中的项2与行2中的项2交换，列表1中的项3与列表3中的项1交换，最后列表2中的项3与列表3中的项2交换。

总而言之:通过交换对角线来进行矩阵求逆。