设某个正整数 Z 并设一个由 N 个非负整数组成的列表，标记为 z0 ... zn-1 什么算法可以找到可以用以下形式表示的 Z 的最小倍数所有 zi * ci 的总和，其中 ci 是任何非负整数常量？
该算法需要运行时间 O(Z * ( N + log(Z) ))。
我尝试使用 djikstras 算法来解决这个问题，并最终确定必须有 Z * N 边和 Z 顶点才能满足时间复杂度要求。我还发现每个 ni 最多可以有 Z 个不同的系数，因为 (min zi)/zi * Z 受 Z 约束。
也许有某种方法可以通过探索循环图设置来做到这一点？
最佳答案
您应该查找Frobenius problem (或麦乐鸡问题)。
给定两个互质整数(a,b)，所有数字>= (a-1)(b-1) + 1都可以写成xa + yb 对于非负整数 x,y。
使用此功能，您的搜索空间将大大减少。
关于算法:找到最小倍数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/30049907/