算法确定线性双方方程的非负值解决方案的存在

StackOverflow https://stackoverflow.com/questions/1467907

  •  13-09-2019
  •  | 
  •  

题

我正在寻找一种方法来确定是否有解决方程的方法：3N1+4N2+5N3 = 456, ， 在哪里 N1，N2，N3 是积极的整数。

或更一般：在那里 零或正 整数 N1，N2，N3...解决方程式 k1n1+k2n2+k3n3 ... = m 在哪里 K1，K2，K3... 和 m 是已知的积极整数。

我不需要找到解决方案 - 只是确定是否存在解决方案。

编辑：

关于该算法的实际使用：

在通信库中，我想在处理消息之前确定给定消息是否根据其大小有效。例如：我知道一条消息包含零或填充的3个字节元素，零或元件的4个字元素和零或元的5个bytes元素。我收到了456个字节的消息，我想在进一步检查其内容之前确定其有效性。当然，消息的标题包含每种类型的元素的数量，但是我想通过经过类似的内容来在通讯上进行第一次检查 pair<MsgType,vector<3,4,5>>.

有帮助吗？

解决方案

您正在问正则表达式

（xxx | xxxx | xxxxx）*

匹配xx ... x，其中x发生456次。

这是O（n+a^2）中的一个解决方案，其中a是左侧的最小数字（在这种情况下为3）。

假设您的数字为6,7,15。我将以6x+7y+15z表格为“可用”数字。您要检查给定号码是否可用。

如果您能够获得一些数字n，那么您肯定可以得到n+6，n+12，n+18-通常，对于所有k> = 0，n+6k。您无法获得一些数字n，那么n-6肯定也不可用（如果可以得到（n-6），则（n-6）+6 = n可以使用），这意味着n-12， N-18，N-6K都不可用。

假设您已经确定15个可用，但9个。在我们的情况下，15 = 6*0+7*0+15*1，但无法以任何方式获得9。因此，根据我们以前的推理，所有k> = 0和9-6k的15+6k可用于所有k> = 0。如果您有一些数字除以6的数字，则为3个（3、9、15、21，...），您可以快速回答：数字<= 9不可用，数字> = 15。

足以确定分区的所有可能剩余的6（即0,1,2,3,4,5）最小的数字是多少。 （我只是证明了其余3的这个数字为15）。

如何做：创建具有顶点0,1,2,3,4,5的图形。对于您给出的所有数字k（7,15-我们无视6）添加X到（x + k）mod 6的边缘。给它重量（x + k）div 6.使用 Dijkstra的算法 使用0作为初始节点。该算法发现的距离将正是我们正在搜索的数字。

在我们的情况下（6,7,15）数字7产生为0-> 1（重量1），1-> 2（重量1），2-> 3（重量1），...，5-> 0（重量1）和数字15给出0-> 3（重量2），1-> 4（重量2），...，5-> 1（重量2）。从0到3的最短路径具有一个边缘 - 其重量为2。因此，6*2 + 3 = 15是最小的数字，其剩余为3。 6*1 + 3 = 9不可用（嗯，我们先前手工检查了）。

与正则表达式有什么联系？好吧，每个正则表达式都有等效的有限自动机，我构建了其中一个。

此问题带有多个查询，出现在 波兰奥林匹克运动会 我翻译了解决方案。现在，如果您现在听到一个人说计算机科学对真正的程序员没有用的人，那就面对他。

其他提示

根据 这个, ，如果{n1，n2，n3，...}的最大常见因素不是m的除数，那么您就没有解决方案。此页面显示了仅{N1，N2}的示例，但它扩展到较大的系统。新问题是编写一种算法来找到最大的共同因素，但鉴于原始问题，这是微不足道的。

因此，您的一部分算法会找到GCF（{n1，n2，...}），然后查看它是否是m的因素。如果不是，则不存在解决方案。这并不能完全表明存在解决方案，但是它可以快速向您显示不存在，这仍然有用。

看起来您在谈论具有整数限制的不平等系统。现实是您正在为该系统解决：

k1n1+k2n2+k3n3...=m
n1 >= 0
n2 >= 0
n3 >= 0

N1，N2，N3是整数。那是一个 线性规划 问题。不幸的是，对您来说，解决这样的系统的一般情况 整数限制是NP完整的. 。但是，有许多算法可以为您解决。

这与 Frobenius硬币问题, ，尚未解决n> 3。

蛮力方法（伪代码）：

def a = 3
def b = 4
def c = 5
def x = 456

for n1 = a to int(x / a) + 1 step a
  for n2 =b to int(x / b) + 1 step b
    for n3 = c to int(x / c) + 1 step c
      if a * n1 + b * n2 + c * n3 = x then
        print n1, n2, n3

也可以看看 http://mail.python.org/pipermail/python-list/2000-april/031714.html

编辑： 在通信库中，这是没有意义的，因为它需要立即工作。在OP的应用程序中，我可能会使用某种哈希，但他的方法听起来很有趣。

这是2个数字案例的东西。我还没有弄清楚如何扩展它：

给定2个相对质量的整数X和Y，存在正整数A和B ax+by=c 对所有人 c>=(x-1)(y-1)

基本上，这有效，因为，如果您假设 x<y, ，您可以用（0，y，2y，3y，...，（x-1）y表达所有整数mod x。现在，通过添加X的一些正倍，您可以在[（X-1）（Y-1），（X-1）Y]之间接触到所有整数，因为（X-1）（Y-）所有整数1）和（X-1）Y-1先前已表示。

  1. GCD（x，y）。如果C不是倍数，请返回false。
  2. 如果GCD（x，y）> 1，则将X，Y，C除以GCD
  3. 如果C>（X-1）（Y-1），请返回true
  4. 否则蛮力

并为蛮力： 

if int(c/y) >= c*y^(-1) mod x, return true, 
else return false

也许以下信息无关紧要，因为它不能解决总体情况，但是...

如果问题是确定是否可以形成给定的正整数k作为总和 3*n1 + 4*n2 + 5*n3, ，对于非负整数N1，N2，N3，则答案为“是”，对于K> = 3。

罗森的著名教科书 离散数学及其应用, ，p。第六版中的287个证明“只能使用4％和5美分的邮票就可以形成12美分或更多的邮费”，使用感应。”

基本步骤是，邮费可以用3个四美分的邮票形成12美分。

感应步骤认为，如果P（K）使用四美分邮票是正确的，那么只需用五美分的邮票代替一个四美分的邮票即可证明P（K+1）是正确的。如果p（k）使用不使用四美分邮票是正确的，那么，因为k> = 12，我们至少需要3五美分的邮票来形成我们的总和，并且可以用4个五美分的邮票替换为4个四美分邮票以实现K+1。

为了扩展上述解决方案，此问题需要仅考虑更多情况。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top