algorithm - 大于或等于目标的数的倍数之和，优化

Question

给定一个等式

喜欢 2(p₁) + 3(p₂) + 7(p₃) >= 257

我需要找到 p₁、p₂、p₃ 的所有可能组合这样上面的陈述是正确的，并且在所有 x_n 已知的情况下，所得总和(等式的左侧)是最小的。

我尝试查找一般情况下的算法，例如

(x₁)(p₁) + (x₂)(p₂) + ( x₃)(p₄) + ... + (x_n)(p_n) >=目标

我遇到了 Knapsack 问题和 Subset-Sum 算法解决方案，但它们并不完全像这个问题。

我在使用 Python 3.x 中的算法之前尝试过，该算法具有 p_n 的下限值，但它仍然以 O( 荒谬的 ) 时间复杂度运行。

显然这里所有的数都是自然数，否则会有无穷解。

Answer 1

我可以看到两种可能的方法，具体取决于 Pi 是否必须 >= 0。Pi >= 0 的情况更明智，所以我会首先考虑。

将其视为动态规划，您可以沿着方程从左到右计算。查看您评论中的较大方程式，首先创建 p0 的贡献列表:0、5、10、15 ... 190384760，在它们旁边是产生它们的 p0 的值:0、1、2， ... 190384760/5。

现在使用此表计算出 5p0 + 7p1 的可能值，方法是组合前两个值:0、5、7、10、12、14...，并保留生成它们所需的 p1 值。

从右到左计算，您将得到一个表格，其中的值最多为 190384755，可以由 p0..p8 的正整数组合创建。您显然只关心最大的一个 >= 190384755。考虑 p8 贡献的所有可能值，从 190384755 中减去这些值，然后在表中查找 p0..p7 以查看其中哪些是可能的。这为您提供了 p8 的所有可能值，并且对于其中的每一个，您都可以递归地重复该过程以打印出 p7 的所有可能值，依此类推重复递归以提供 p0..p8 的所有值，从而产生最低值超过190384755。这与子集和的伪多项式算法非常相似。

如果Pi可以<0，那么可以达到的值都是Pi的gcd的倍数，很可能都是整数，这个有无穷多个解。如果这真的是你想要的，你可以从阅读 http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm 开始。 .