将转型成本降至最低

Question

我想出了以下问题，但我找不到解决方案。

声明：

一共有N个酒杯。假设每个酒杯都有无限的容量。每个玻璃杯中的酒量是一个正的非零整数，其中单位是ml。类型-1的移动被定义为将一毫升从玻璃杯i转移到玻璃杯j。类型2的移动被定义为从玻璃杯i中丢弃一毫升。所有类型-1的移动的成本为1。类型2的所有移动都有k的成本。给定每个杯子中的初始葡萄酒数量，我们需要进行两种类型的移动，以确保每个杯子中的葡萄酒数量是质数(或零)。打印此类转换的最低成本。

如何解决这个问题？对可能的解决方案有什么想法吗？

Answer 1

以下是我的想法的粗略草图：

质数的分布方式是这样的x/ln(x)。

还可以使用该页面上的边界来查找与该酒杯中的酒量最接近的质数。

在找到这些数字之后，您可以将问题简化为一个具有边的图，这些边具有表示从一个玻璃移动到另一个玻璃的值的成本(您的类型1移动)。这些节点就是眼镜本身。

从这里开始，你就有了一个图问题，你必须在这个图中考虑最小成本的路径。你的目标是找到一条成本最低的路径，使所有的玻璃都是质数。

如果有阻止你这样做的玻璃杯，喝了它们(类型2移动)，葡萄酒对你有好处:)

更新

我将在这里写下我们在聊天中讨论的一些有效想法：

这里提到了

• bipartite matching，有一种可能性，这个问题可以简化为，

，

• ，你可以首先得到两个玻璃之间的prime partitions (每两个玻璃之和的质数分区)，这些分区是图中的边。然后，还可以为类型2移动添加边。您可以以某种方式关联成本，然后运行minimum flow algorithm来解决问题
• 问题也可能是您需要上面提到的所有边作为最优解决方案可能并不意味着为每个眼镜选择最优prime parititon

Answer 2

这种类型的问题可以通过动态编程来解决，它类似于计算字符串的最小编辑距离，可以使用Hirschberg's Algorithm来解决。

这里实际上有两个阶段。首先，你必须找到候选的质数组合，然后计算到这些候选组合的最小编辑距离。具有最小编辑距离的是答案。

例如，假设你有像16 14 8这样的总数。第一步是你必须枚举每个可能的素数组合：{ 37 0 0}{ 31 7 0 }，等等。然后你使用Hirschberg算法来计算到每个候选者的最小编辑距离。