python – 0/1背包几个变量：哪种算法？

发布时间：2020-12-20 13:28:33 所属栏目：Python 来源：网络整理

导读：我必须使用约束来实现0/1背包问题的解决方案. 在大多数情况下,我的问题很少有变量(~10-20,最多50). 我从大学回忆起,有许多算法在许多情况下比蛮力更好(我想,例如,分支定界算法). 由于我的问题相对较小,我想知道在使用复杂的解决方案而不是蛮力时,效率方面是

我必须使用约束来实现0/1背包问题的解决方案.
在大多数情况下,我的问题很少有变量(~10-20,最多50).

我从大学回忆起,有许多算法在许多情况下比蛮力更好(我想,例如,分支定界算法).

由于我的问题相对较小,我想知道在使用复杂的解决方案而不是蛮力时,效率方面是否有明显的优势.

如果它有帮助,我用Python编程.

如果权重之和足够小,您可以使用伪多项式算法,该算法使用动态编程.你只需计算,你是否可以为每个X和Y获得前Y项的重量X.
这在时间O(NS)中运行,其中N是项目数,S是权重之和.

另一种可能性是使用中间相遇方法.将项目分成两半并：对于前半部分,采取每种可能的项目组合(每半部分有2 ^(N / 2)种可能的组合)并将其权重存储在某些集合中.下半场采取各种可能的项目组合,检查上半部是否有合适的重量组合.这应该在O(2 ^(N / 2))时间内运行.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!