algorithm - 如何在容器之间对加权项目进行平均排序？

Question

我最近一直在尝试设计一种算法来对 n 个容器之间的加权项数组进行排序，以便每个容器的加权和尽可能相等。

大约一个小时后，我当前的草稿包括将加权值从大到小排序，并将未排序数组中剩余的最大值排序到总和值最小的容器中(如果最小总和与另一个的总和相等)列，算法将随机选择)。排序后的值随后将从未排序的数组中删除。

目前，在我可以就其准确性咨询一些更有经验的人之前，我不会对此进行编码。我没有接受过正式的 CS 培训，但熟悉一些算法。我最初查看了背包问题的解决方案，但发现很难翻译，因为我的示例包含多个容器。

通过手动将其应用于电子表格中的少数值来粗略测试我最早的草稿似乎表明它可以正常运行。

考虑到所有这些，请考虑以下事项:

• [A]:目前的草案是否有效？
• [B]:它是最高效的版本吗？
• [C] : 如果不是，那是什么？

提前感谢任何愿意提供帮助的人。

解决方案:在 reddit 上询问后，很明显这只是分区问题的一个实现。澄清一下，在此之前我错误地将分区称为容器。

Answer 1

如果我正确理解您的算法，一般来说似乎不正确。一个反例是两个容器和重量为 10、5、3、3、3、3、3 的元素。正确的解决方案是 10 + 5 = 3 + 3 + 3 + 3 + 3。

一旦您的方法将 10 和 5 放入不同的容器中，它就会丢失，因为两个容器都无法通过添加任意数量的 3 来达到 15，并且最均等的分布每个容器中都有 15。