总使用物品限额的背包

Question

所以，我有一个背包，其中可以放入背包的物品数量是有限制的，而物品的重量也有限制。在

因此，给定项目限制5，重量100： 我们会找到5个项目（可以重复5倍相同的项目）最适合重量100。在

我解决了动态规划中的无界和有界（每个项目都有一个限制，但使用的项目总数没有限制）。但我有点不明白怎么做这个新方法。这是一个多维背包问题吗，比如体积和重量？但是，我们要的是物品的使用和重量？或者是一个0比1的背包？在

如果有人能把这一点分解成更小的逻辑步骤，或者给我指出一些可靠的代码来阅读（我的googlefu正在努力寻找解决方案），我将不胜感激。在

感谢您抽出时间！在

Answer 1

这可以表述为一个多重约束背包问题（也称为多维背包问题）。在

目标函数和第一个维度与当前公式中的相同（即权重总和）。在

然后可以使用第二个维度来约束所选项目的数量。使用Wikipedia notation：

• w_2，i=1所有i
• W₂=允许选择的项目数限制（在您的示例中，为5）。在

以下是一些参考资料：

• https://en.wikipedia.org/wiki/List_of_knapsack_problems#Multiple_constraints
• https://pdfs.semanticscholar.org/42c7/3dfb22d04da507ebe8df62c697e5263f84a0.pdf
• https://homepages.laas.fr/elbaz/EJIE.pdf

Answer 2

这就是多重约束背包问题。你的新限制是，项目数量之和小于一些与它们的重量无关的数字。在

这里有一些很好的方法：http://www2.math.uni-wuppertal.de/~klamroth/publications/klwidp00.pdf

你也应该尝试用新的约束来调整正则背包问题的递归关系，看看你得到了什么。在