algorithm - 使用乘积的下界最小化总和

Question

我有一个优化问题，目前正在通过蛮力解决，但我希望有更好的方法。

问题:给定n和 d , 求素幂 p1^e1, ..., pk^ek ( pi 是不同的)使得

1. p1^e1 * ... * pk^ek >= n^d
2. p1^e1 + ... + pk^ek < n是最小的

我目前的解决方案是遍历所有可能的素数子集(直到某个固定数)，然后遍历所有可能的指数(直到某个固定数)，然后测试条件 1，然后查看总和是否最小迄今为止。这需要很长时间。我可以做一些更聪明的事情来加快速度吗？

Answer 1

这看起来像一个 knapsack problem .我怀疑它是NP完全的。事实上，如果 (d = 1)，优化 可能等同于因式分解。

然而，并非所有背包问题都是 NP-hard - 这就是 Merkle–Hellman 背包密码系统被破解的原因。