algorithm - 寻找解决独特问题的算法

我有六个数组，每个数组都有一个（不一定是唯一的）从一到五十的值。我还得到了一些要在它们之间拆分的项目。每个项目的值由它所在的数组定义。数组可以包含无限或零个项目，但所有数组中的项目总和必须等于给定的原始项目数。

我想找到数组中项目的最佳配置，其中每个单独数组中的项目值之和尽可能接近。

例如，假设我有三个值为 10 的数组和三个值为 20 的数组。对于九个项目，一个将进入每个“20”数组，两个将进入每个“10”数组，使得每个数组的总和为 20，项目总数为 9。

我无法将小数项添加到数组中，并且这些数字几乎不可能像那个示例那样完美整除，但总有一个解决方案，总和之间的差异很小。

我目前正在使用蛮力来解决这个问题，但性能会受到大量项目的影响。我觉得这个问题有一个数学答案，但我什至不知道从哪里开始。

标签： algorithmmathlinear-algebramathematical-optimizationalgebra

编写一个贪心算法很容易得出一个近似解。只需始终将下一项添加到具有最低值总和的数组中。

具有最高值的数组应该在 1 项内是正确的。

对于数组中具有最高值的每个项目计数，您可以重复该练习。使具有第二高值的数组在 1 以内。

继续遍历所有这些，使用 6 个数组，您最终会得到3^5 = 243可能的项目排列（请注意，最后一个数组中的项目数完全由前 5 个决定）。选择其中最好的一个，你的组合爆炸就会被包含在内。

（如果您试图最小化最大和最小数组之间的值差异，并且具有固定数量的数组，则此方法应该有效。）