algorithm - 重量平衡器算法

Question

问题

给定一系列具有不同重量的元素和一定数量的可以存储重量的容器，找到平衡容器中重量的解决方案集。最优解将最小化重量最大的容器和重量最小的容器之间的差异。

条件

• 必须使用所有的权重
• 不能将重量分装到单独的容器中

申请

该算法的实际应用是尝试在实时操作系统中对调度进行负载平衡。权重是每个调度函数的运行时间，容器是函数可以调度运行的帧。这样你就可以尝试分散每个函数的运行时间，以尽量减少整体帧时间。

想法

这似乎是 1/0 多背包问题和装箱问题之间的交叉。我正在尝试提出一种使用动态编程来解决问题的算法。我正在努力寻找如何使用它来解决这个问题。有没有人对类似问题有任何建议或 Material ？

Answer 1

您可以使用贪心算法。随机取重量，并将每个重量添加到重量最小的容器中。重复该过程，直到运行 n 次算法后仍找不到更好的解。