algorithm - 重复模式中的整数分解

Question

我正在为特定的整数分解案例寻找有效的解决方案。我所说的高效是指比我目前拥有的 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
• 每次重复都会向公式中添加一些内容，但没有任何更改(约束除外)

有什么想法吗？

Answer 1

首先这个词是错误的。它不是 integer factorization ，而是一个线性 diophantine equation有许多变量和一些额外的约束。

没有你的限制，这将是一件容易的事。只需找到 GCD(list of coefficients) 并且如果它除以自由项 - 您有一个解决方案，否则没有。

有了您的约束，这可能是第一步，但在这里，如果您看到有解决方案，它们可能不满足约束。

---

我没有看到一个快速的(多项式解)所以我将如何解决它。你有

我会在 middle approach 中使用 meet并将带有约束的方程式分为两部分:

第 1 部分是 ,

第 2 部分 是

我会将它们分开，以便在两个部分中执行的计算数量大致相同(考虑到约束)。

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

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

---

这math answer可能会帮助某人想出一个我找不到的更好的方法。