3

我正在寻找整数分解的特定情况的有效解决方案。高效我的意思是比我目前拥有的要快得多O(2^n)（n 表示我们完成后数组中的元素数）。

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

我们想知道是否可以满足4*a + 5*b + 11*c = 84，

给定以下约束：

  • 0 <= 一 <= 3
  • 0 <= b <= 2
  • 0 <= c <= 1

如果我们没有找到解决方案，我们将一个整数添加到数组中，比如 15：[4, 5, 11, 15]

现在我们想知道是否有任何满足4*a + 5*b + 11*c + 15*d = 84

鉴于

  • 0 <= 一 <= 4
  • 0 <= b <= 3
  • 0 <= c <= 2
  • 0 <= d <= 1

...然后我们重复这个过程，直到找到解决方案，或者最多 n 次。我想知道我们是否可以利用问题的重复性来找到有效的解决方案：

  • “目标”不变
  • 整数按升序排列
  • 每次我们添加一个新元素时，a,b,c... 的最大约束增加 1
  • 每次重复都会将某些内容添加到公式中，但没有任何更改（约束除外）

有任何想法吗？

4

1 回答 1

3

首先这个词是错误的。它不是整数分解，而是一个线性丢番图方程，其中包含许多变量和一些额外的约束。

没有你的约束，这将是一件容易的事。只要找到GCD(list of coefficients)它，如果它划分了免费期限 - 你有一个解决方案，否则它没有。

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

我没有看到快速（多项式解决方案），所以这就是我将如何解决它。你有在此处输入图像描述

我将在中间方法中使用 meet并将具有约束的方程分为两部分：

第 1在此处输入图像描述部分是

第 2 部分是在此处输入图像描述

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

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

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

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

于 2016-01-08T00:26:23.187 回答