最小化转型成本

Question

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

问题陈述：

有N个酒杯。假设每个酒杯的容量都是无限的。每个酒杯中的酒量是一个正非零整数，单位为毫升。类型1移动被定义为将一毫升从杯子i转移到杯子j。类型2移动被定义为从杯子i丢弃一毫升。所有类型1移动的成本为1。所有类型2移动的成本为k。给定每个杯子中初始的酒量，我们需要进行某些类型1或类型2的移动，以确保每个杯子中的酒量是一个质数（或零）。输出这种变换的最小成本。

如何解决这个问题? 有什么可能的解决方案吗?

- Guru Prasad

Answer 1

这是我想法的草图：

质数分布如x/ln(x)。

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

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

从这里开始，您将面临一个图形问题，必须考虑在此图形中具有最小成本的路径。您的目标是找到一条通往所有玻璃都是质数的状态的最小成本路径。

如果有阻止您这样做的酒杯，请喝掉它们（类型2移动），葡萄酒对您有好处：）

更新：

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

• 二分图匹配被提到，有可能问题可以被简化为此
• 你可以先得到每两个杯子之间的质数分割（每两个杯子之和的质数分割），这些分割是一个图中的边。然后，你还要添加类型-2移动的边。你可以以某种方式关联成本，然后运行最小流算法来解决问题
• 问题也可能是你需要所有上述边作为最优解可能不意味着对每个杯子都采取最优质数分割

- wsdookadr

---

我有一个类似的想法。我考虑将所有杯子中的初始酒量相加。之后，我们可以找到最接近该总和且可表示为质数之和的小于或等于该总和的数字。但是，我们需要找到杯子中的金额和构成总和的质数之间的一一对应关系，并且该映射必须具有最小成本。不确定如何完成后半部分。如果您有一些想法，请帮助我。 - Guru Prasad

你可以使用离散背包来找到与上述总和相等的质数。但是，你需要反转背包中物品相关的成本，因为在你的问题中，你想要最小化成本，而不是最大化它，而背包的经典公式是最大化成本 :) 然后，我上面描述的图形就不再需要了。 - wsdookadr

是的，我可以通过使用动态规划来实现第一部分。我想知道如何找到初始金额和质数之间的双射，使其具有最小成本。我该如何将其建模为图问题？ - Guru Prasad

我认为图表不再需要了。你可以直接使用经过上述自定义的经典背包算法。成本可以通过找到每个杯子中葡萄酒数量最近的质数来确定。 - wsdookadr

但我发现选择最近的质数可能并不总是导致最优解，因为质数之间的间隔是一个递增函数。我可以找到一个例子，证明这种方法可能行不通。 - Guru Prasad

让我们在聊天中继续这个讨论。点击此处进入聊天室。 - Guru Prasad

Answer 2

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

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

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

- Tyler Durden

---

谢谢 :) 我会等待看看是否有人能提出更好的解决方案。 - Guru Prasad