我正在努力解决以下问题：
给定n整数，将它们放入mbin 中，以使所有 bin 中的总和最小化。诀窍是，一旦将数字放入箱中，箱的总重量/成本/总和将以非标准方式计算：
weight_of_bin = Sigma - k * X其中Sigma，bin 中的整数和是 bin
k中的整数个数，是
X位于 bin 中的整数所共有的素数除数的数量。
换句话说，通过将具有许多共同素因数的数字组合在一起，并将不同数量的数字放在不同的 bin 中，我们可以在总和中实现一些“节省”。
我使用装箱公式，因为我怀疑问题出在 NPhard 上，但我很难找到证据。我不是数论专家，我对垃圾箱的重量取决于垃圾箱中的物品这一事实感到困惑。
这类问题有硬度结果吗？
PS我只知道数字是整数。问题中涉及的最大整数没有明确的限制。
感谢您提供的任何指示。
This is not a complete answer, but hopefully it gives you some things to think about.
First, by way of clarification: what do you know about the prime divisors of the integers? Finding all the prime divisors of the integers in the input to the problem is difficult enough as it is. Factorization isn't known to be NP-complete, but it also isn't known to be in P. If you don't already know the factorization of the inputs, that might be enough to make this problem "hard".
In general, I expect this problem will be at least as hard as bin packing. A simple argument to show this is that it is possible that none of the integers given have any common prime divisors (for example, if you are given a set of distinct primes). In which case, the problem reduces to standard bin packing since the weight of the bin is just the standard weight. If you have a guarantee about how many common divisors there may be, you may possibly do better, but probably not in general.
There is a variant of bin packing, called VM packing (based on the idea of packing virtual machines based on memory requirements) where objects are allowed to share space (such as shared virtual memory pages). Your objective function, where you subtract a term based on "shared" prime divisors reminds me of that. Even in the case of VM packing, the problem is NP-hard. If the sharing has a nice hierarchy, good approximation algorithms exist, but they are still only approximations.