首页 文章

复杂的0/1背包,有多个隔层

提问于
浏览
0

假设我的背包里有3个隔层:红色,绿色,蓝色和3套物品:红色物品,绿色物品和蓝色物品都有重量和好处 . 我还要求必须在背包的每个隔间中放置总物品总数 . Red Redpartment必须有2个红色项目,Green Compartment必须有3个绿色项目,蓝色隔间必须有3个蓝色项目 . 我的背包可以承受某种最大重量 . 我需要在给定一定重量的情况下优化最大值 .

为了解决这个问题,我尝试使用用于解决0/1回退的分支定界技术 . 这种技术可以快速计算,但会选择在空间上留下太多空间并且不会返回最佳项目的项目 .

可以使用哪些技术在合理的时间内解决这个问题(也就是说,不是强制执行所有可能的组合)?我不熟悉动态编程,但这是更适合的东西还是我可以使用的不同技术?

1 回答

  • 2

    非常有趣的问题!是的,这个问题可以通过动态编程来解决 .

    要了解如何解决,首先需要了解如何使用动态编程解决背包:http://en.wikipedia.org/wiki/Knapsack_problem .

    你可以看到解决Knapsack的递归函数只有一个参数,即剩余权重 . 要修改你的问题,你需要沿着另外三个参数“拖动”,这些参数存储了我们所处的每个隔间条件的接近程度 . 因此递归函数有4个参数 .

    希望这可以帮助 .

相关问题