algorithm - 最大化由乘积之和组成的方程，然后用一个数取模

Question

我需要一个公式来计算变量和常量乘积的最大总和，然后将整个总和乘以某个数字进行取模。

X = (C1*x1 + C2*x2 + C3*x3..... )%M，我们这里要最大化'X'，给定Ci和M的值，所有xi都是变量(非- 负整数，包括零)，简而言之，我可以说我们必须改变 xi，以便我们获得最大可能的 X，例如

X = (10*i + 3*j)%18(这里i和j是变量，即非负整数)

答案:- X = 17(取 j = 1 和 i = 5)

是否存在找到 X 的最大可能值的公式？

对不起，如果你不明白这个问题(我的英语不好)，如果你有任何疑问，请在评论部分提问

Answer 1

如果存在一个与 M 互质的 C，则存在一个 x 使得 Cx = M - 1 (mod M)；将所有其他 x 设置为 0，并将与我们的特殊 C 对应的那个设置为所需的值。没有比 M - 1 (mod M) 更好的了。

否则，如果有两个互质 C，比如 C1 和 C2，则可以获得任何大于 (C1 - 1)(C2 - 1) - 1 的和(查看硬币问题，或 Frobenius 数);因为一定存在比 M - 1 (mod M) 更大的数，所以这已经是你能做的最好的了；将其他所有x设为0，求得M-1所需的x1、x2。

否则，通过首先将所有 C 与 M 直接比较，然后将所有 C 相互比较，找到最小最大公约数。设这个最小最大公分母为m。然后，可以使用上述方法修改得到M - m (mod M)。但是，不可能达到 M - 1 或任何高于 M - m (mod M) 的值，因为所有数字都有一个公因数。

要真正找到这些案例中的数字，我认为首先要确定案例；然后，按照策略(1 或 2 个非零项)简单地迭代可能性。由于我们已将其缩小到一到两个术语，因此这并不可怕。可能有更聪明的方法来完成此任务...如果需要比检查可能性更复杂的方法，请发表评论，我将重新讨论。

更新

评论表明对第三种情况(没有互质系数)的处理是不正确的，而且是不正确的。考虑 C1 = 14，C2 = 21，M = 6 的情况。上面概述的方法发现最小成对 GCD 为 2，并表示可达到的最大值为 6 - 2 = 4；但是，您只需取 x1 = 1 和 x2 = 1 即可得到 5 (mod M)。也许要获得正确答案真正需要做的是考虑所有成对 GCD 并对它们应用相同的推理。也就是说，我们的成对 GCD 是 2、3 和 7。通过 n = 2 的硬币问题的解决方案，这意味着通过组合每一对我们可以获得这些 GCD 的足够大倍数的任何数字。这意味着，模 M，GCD 本身是可以实现的；所以我们可以递归地将上述解决方案应用于成对的 GCD，直到所有成对的 GCD 共享一个共同的术语(那么我的原始案例分析是正确的)；或者，成对 GCD 之一变为 1，在这种情况下答案为 M - 1。

请注意，沿途跟踪递归和案例以根据原始 C 重建正确答案可能是可能的。留作练习。

更新:

根据评论，我现在将尝试将此(固定的？)方法应用于真实示例。

M, C1, C2 = 385, 42, 30
GCD(M, C1) = 7
GCD(M, C2) = 5
GCD(C1, C2) = 6

  7 and 5 are coprime so we can get any number greater than (7-1)(5-1)-1
  any number greater than 23 is obtainable
  384 = 2*[7] + 74*[5]

  7 is obtainable
  7 = 46*[42]

  5 is obtainable
  5 = 13*[30]

  combining, we get
  384 = 2*[7] + 74*[5]
      = 2*46*[42] + 74*13*[30]
      = 92*[42] + 962[30]
      ~ 92*C1 + 192C2