以最少的更改成本为每个组选择最佳 ID
Choose best id for each group with least change cost
我想为每个组分配唯一的id，但需要限制更改成本。
如下图，共有4组(h1, h2, h3, h4)。有 3 个 id (id1, id2, id3)。更改组的现有 id 将需要成本，例如，更改 h1 的 id1 将花费 4.
我想将这3个id分配给4组中的3组，并为另一组分配一个新的id。我们的目标是我们需要一个 改变成本 最少的解决方案。
在下面的例子中，如果我们最终为H1分配id3，那么从H1开始的变化成本就是7。总的变化成本是每个成本的总和组.
举个例子，例子的最佳解法是：
H1 <- id2, H2 <- New ID, H3 <- id3, H4 <- id1。更改成本为 8.
目前我使用的是暴力破解，效率不高，尤其是当group/id的数量增加时。
有什么建议吗？
示例：
id1 id2 id3
H1 4 3 0
H2 1 0 0
H3 2 0 2
H4 3 1 0
你可以在这里使用min-cost max flow
将 source 连接到容量为 1 的所有 id，将每个 id 连接到容量为 1 和 cost -a[id[i], h[j]] 的每个 h（因为您实际上需要找到最大值），
然后将所有 hs 连接到容量为 1 的接收器。
应用 min-cost max flow 后，您将在那些 (i, j) 中获得流量，您应该将第 i 个 id 分配给第 j 个 h。其他 hs 的新 ID。
我想为每个组分配唯一的id，但需要限制更改成本。
如下图，共有4组(h1, h2, h3, h4)。有 3 个 id (id1, id2, id3)。更改组的现有 id 将需要成本，例如，更改 h1 的 id1 将花费 4.
我想将这3个id分配给4组中的3组，并为另一组分配一个新的id。我们的目标是我们需要一个 改变成本 最少的解决方案。
在下面的例子中，如果我们最终为H1分配id3，那么从H1开始的变化成本就是7。总的变化成本是每个成本的总和组.
举个例子，例子的最佳解法是：
H1 <- id2, H2 <- New ID, H3 <- id3, H4 <- id1。更改成本为 8.
目前我使用的是暴力破解，效率不高，尤其是当group/id的数量增加时。
有什么建议吗？
示例：
id1 id2 id3
H1 4 3 0
H2 1 0 0
H3 2 0 2
H4 3 1 0
你可以在这里使用min-cost max flow
将 source 连接到容量为 1 的所有 id，将每个 id 连接到容量为 1 和 cost -a[id[i], h[j]] 的每个 h（因为您实际上需要找到最大值）， 然后将所有 hs 连接到容量为 1 的接收器。
应用 min-cost max flow 后，您将在那些 (i, j) 中获得流量，您应该将第 i 个 id 分配给第 j 个 h。其他 hs 的新 ID。