给定一个等式
喜欢 2(p1) + 3(p2) + 7(p3) >= 257
我需要找到 p1、p2、p3 的所有可能组合 这样上面的陈述是正确的，并且在所有 xn 已知的情况下，所得总和(等式的左侧)是最小的。
我尝试查找一般情况下的算法，例如
(x1)(p1) + (x2)(p2) + ( x3)(p4) + ... + (xn)(pn) >=目标
我遇到了 Knapsack 问题和 Subset-Sum 算法解决方案，但它们并不完全像这个问题。
我在使用 Python 3.x 中的算法之前尝试过，该算法具有 pn 的下限值，但它仍然以 O( 荒谬的 ) 时间复杂度运行。
显然这里所有的数都是自然数，否则会有无穷解。
最佳答案
我可以看到两种可能的方法，具体取决于 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 开始。 .
关于algorithm - 大于或等于目标的数的倍数之和，优化，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/21472964/