给定一个方程
比如 2(p 1 ) + 3(p 2 ) + 7(p 3 ) >= 257
我需要找到 p 1、 p 2、 p 3的所有可能组合，这样上述陈述是正确的，并且在所有 x n都已知 的情况下，得到的总和（等式的左侧）是最小的。
我尝试为一般情况查找算法，例如
(x 1 )(p 1 ) + (x 2 )(p 2 ) + (x 3 )(p 4 ) + ... + (x n )(p n ) >= 目标
我遇到了背包问题和子集和算法解决方案，但它们并不完全像这个问题。
我在 Python 3.x 中使用具有 p n下界值的算法之前尝试过，但它仍然以 O（荒谬）的时间复杂度运行。
显然这里的所有数字都是自然数，否则将有无限的解决方案。
也许给定的例子只是一个玩具箱。
如果不是，穷举搜索是相当可行的：最小和以 259 为界（组合 0、0、37），并且在此范围下的组合少于 50 万个。
此外，如果您设置两个变量，例如 p2 和 p3，使得 3(p2) + 7(p3) < 257，则很容易找到最小的 p1，使得 2(p1) + 3(p2) + 7(p3) >= 257。你只需要尝试 3200 (p2, p3) 左右的组合。
我可以看到两种可能的方法，具体取决于 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开始。