我有一些像这样的物品清单:
[ ["orange", 9], ["watermelon", 3], ["grapefruit", 6], ["peach", 8], ["durian", 2], ["apricot", 6] ]
我想将此列表分为…说两组,以便每组中项目的权重之和尽可能相等,即:
List 1: orange: 9 durian: 2 apricot: 6 TOTAL: 17 List 2: watermelon: 3 grapefruit: 6 peach: 8 TOTAL: 17
目前,我正在通过以Z字形方式遍历有序列表来解决此问题。将第一遍的权重较高的项目分配给每个组,在第二遍的权重较低的项目进行辅助,依此类推。
可以,但是有缺陷。我在想,如果我在组之间进行第二次交换(在组之间交换项目),将导致组分布更加均匀,但是所涉及的代码可能会变得过于复杂。
有人知道这样做的更有效或更智能的方法吗?
谢谢!
这是分区问题的优化版本,它是NP完全的,尽管根据该文章,“在许多情况下,都有启发式方法可以最佳或近似地解决该问题。”
该文章的方法部分包含许多方法来进行近似或伪多项式解。具体来说,如果您可以得到一个近似的答案,则可以尝试贪婪的方法:
模仿贪婪算法是解决问题的一种方法,该算法模仿孩子选择游戏团队的方式,该算法按降序遍历数字,将每个数字分配给总和较小的子集。
这种方法的运行时间O(n^2)可以确保达到精确解决方案的四分之三。
O(n^2)
如果您必须有一个精确的解决方案并且您的数据集足够小,则可以始终采用蛮力方法来生成所有可能性(这是指数的O(2^n))。根据您的性能需求,这可能就足够了。
O(2^n)