重复模式下的整数分解

Question

3

我正在寻找一个高效的解决方案来解决特定的整数因子分解问题。这里的“高效”是指比当前的 O(2^n) 要快很多（其中n表示我们完成后数组中元素的数量）。

假设我们有以下数组：[4, 5, 11]，并且一个“目标”值为84。

我们想要找出是否有可能满足 4*a + 5*b + 11*c = 84，

给定以下限制条件：

0 <= a <= 3

0 <= b <= 2

0 <= c <= 1

如果我们没有找到解决方案，则向数组添加一个整数，比如15：[4, 5, 11, 15] 现在我们想知道是否有任何满足 4*a + 5*b + 11*c + 15*d = 84 的东西

给定以下限制条件：

0 <= a <= 4

0 <= b <= 3

0 <= c <= 2

0 <= d <= 1

...然后我们重复这个过程，直到找到一个解决方案，或达到n次。我想知道是否可以利用问题的重复性质来找到一个高效的解决方案:

目标不会改变

整数按升序排列

a、b、c…的最大约束每次增加1个

每重复一次都会向公式添加一些内容，但除了约束条件外什么都没有改变。

有什么想法吗？

- Atte Juvonen

1

当你有了第一个公式（包括a、b和c）的解决方案后，你可以将完全相同的解决方案用于所有其他公式，只需将剩余变量（d、e等）设置为0即可。 - Amit

哦，抱歉如果我用了错误的术语。这个应该叫什么？ - Atte Juvonen

@Amit 一旦我们找到了解决方案（在任何步骤），我们就可以停止这个过程。我会将这些信息编辑到问题中。 - Atte Juvonen

1

如果我没错的话，这个问题属于“整数线性规划”类别，已知它是NP难问题。因此，没有希望找到快速（多项式）解决方案。 - user1196549

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Salvador Dali · Accepted Answer

首先，术语是错误的。它不是整数分解，而是带有许多变量和一些附加约束条件的线性丢番图方程。

如果没有你的限制条件，这将是一个简单的任务。只需找到GCD(系数列表)，如果它可以整除自由项，则存在一个解，否则不存在。

对于你的限制条件，这可能是第一步，但是如果你发现有解，它们可能不符合限制条件。

我没有看到一个快速的（多项式解）方法，所以这是我会处理它的方式。你有

。

我会使用meet in the middle approach，并将带约束条件的方程分为两部分： 第一部分是

, 第二部分是

我会将它们分开，使得两个部分中执行的计算数量大致相同（考虑到约束条件）。

现在你需要迭代第一部分并将所有内容存储在字典中。然后迭代第二部分并检查答案是否存在于字典中。如果是，你就找到了一个解决方案。

这将指数除以2，但需要内存。

这个数学答案可能会帮助某人想出比我找到的更好的方法。