所以,我有一个背包,可以放入背包的元素数量是有限制的,而元素的重量也有限制。
所以给定元素限制 5,重量 100: 我们会找到最适合体重 100 的 5 件元素(可以重复 5 次相同的元素)。
我已经解决了动态规划中的无界和有界(每个项目都有限制,但使用的项目总数没有限制)。但是我对如何使用这种新方法有点困惑。这会是一个多维背包问题,例如体积和重量吗?但是相反,我们想要元素的使用和重量?还是改款后的0-1背包?
如果有人能够将其分解为更小的逻辑步骤或向我指明要阅读的可靠代码的方向(我的 google-fu 正在努力寻找解决方案),将不胜感激。
感谢您的宝贵时间!
最佳答案
这是多重约束背包问题。您的新约束是项目数量的总和小于与其重量无关的某个数字。
这里有一些好的方法:http://www2.math.uni-wuppertal.de/~klamroth/publications/klwidp00.pdf
您还应该尝试使用新约束调整常规背包问题的递归关系,看看结果如何。
关于python - 限制使用元素总数的背包,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/45977151/