我有一个优化问题，我目前正在通过蛮力解决，但我希望有更好的方法。
问题：给定nand d，找到素数幂p1^e1, ..., pk^ek（pis 是不同的）使得
p1^e1 * ... * pk^ek >= n^dp1^e1 + ... + pk^ek < n是最小的
我目前的解决方案是遍历所有可能的素数子集（直到某个固定数），然后遍历所有可能的指数（直到某个固定数），然后测试条件 1，然后查看总和是否是迄今为止最小的。这需要很长时间。有什么更聪明的方法可以加快速度吗？
问问题
345 次
2 回答
1
这似乎是一个背包问题。我怀疑它是NP完全的。事实上，如果 (d = 1)，优化可能等同于分解。
然而，并非所有的背包问题都是 NP 难题——这就是 Merkle-Hellman 背包密码系统被破解的原因。
于 2013-03-11T07:51:43.303 回答
0
通过 AM-GM 不等式并使用其他约束，您可以获得：
(n / k)^k > 产品 >= n^d
因此 n^(kd) > k^k。将 log 以 n 为底，我们得到：kd > k*log(k)。由于 k <= n (基于总和) k * (1 - log(k)) > d
您可以绘制上面的 LHS 以获得 k 的估计值。
于 2013-03-11T10:12:37.877 回答