1

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

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

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

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

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

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

4

3 回答 3

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 交易获得平等。

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

于 2013-03-06T13:42:58.170 回答
1

假设您总共有 x1 个种类 1、...、xn 个种类 n 的资源。

假设您有 k 个人，并且每个人都有（或需要分别以 y1、y2、...、yk 资源结束。

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

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

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

于 2013-03-06T01:29:32.837 回答
0

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

{ 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 交换。

总结一下：通过对角线交换来进行矩阵求逆。

于 2013-03-05T23:36:52.943 回答