algorithm - 最大限度地降低转型成本

Question

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

陈述：

有N个酒杯。假设每个酒杯都有无限容量。每杯酒的量是一个非零正整数，单位是毫升。类型 1 的移动定义为将 1 ml 从玻璃 i 转移到玻璃 j。类型 2 的移动定义为从玻璃 i 中丢弃一毫升。所有类型 1 的移动的成本为 1。所有类型 2 的移动的成本为 k。给定每杯酒的初始数量，我们需要对这两种酒做一些移动，以确保每杯酒的数量是素数（或零）。打印这种转换的最低成本。

如何解决这个问题？任何可能的解决方案的想法？

Answer 1

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

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

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

Answer 2

这是我的想法的粗略草图：

素数分布如下x/ln(x)。

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

找到这些数字后，您可以将问题简化为带有边的图形，边的成本代表从一个玻璃杯移动到另一个玻璃杯的值（您的类型 1 移动）。节点将是眼镜本身。

从这里开始，您将面临一个图表问题，您必须考虑该图表中最小成本的路径。您的目标是找到一条成本最低的路径，该路径导致所有眼镜都是素数的状态。

如果有玻璃杯阻止您这样做，请喝它们（2 型移动），葡萄酒对您有好处 :)

更新：

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

• 提到了二分匹配，并且有可能将问题简化为
• 您可以首先获取每 2 个眼镜之间的主要分区（每 2 个眼镜之和的主要分区），这些分区是图中的边。然后，您还为类型 2 移动添加边。您可以以某种方式关联成本，然后运行最小流量算法来解决问题
• 问题也可能是您需要上面提到的所有这些边缘，因为最佳解决方案可能并不意味着为每个眼镜采用最佳素数parititon