背包数量限制 [英] Knapsack with limit on total items used

问题描述

因此，我有一个背包，其中可以放入背包的许多物品有限制，而物品的重量也有限制.

So, I have a knapsack where a number of items that can be placed into the knapsack has a limit, while the amount of weight of the items also has a limit.

因此给定项目限制5，重量为100: 我们会找到最适合重量100的5个项目(可以重复5个相同的项目).

So given item limit 5, and weight 100: We would find the 5 items (can repeat 5x same item) that best fit weight 100.

我在动态编程中解决了无界和有界(每个项目都有限制，但使用的项目总数没有限制)的问题.但是我对如何执行这种新方法感到有些困惑.这将是一个多维背包问题，例如体积和重量吗?但是，我们需要物品的使用量和重量吗?还是是有变化的0-1背包?

I have solved both unbounded and bounded(each item has a limit, but the total amount of items used has no limit) in dynamic programming. But I'm a bit confused with how to do this new approach. Would this be a multidimensional knapsack problem, like volume and weight? But instead, we want item's used and weight? Or is it a 0-1 knapsack with alterations?

如果有人能够将其分解为较小的逻辑步骤，或者将我指向一些可靠的代码阅读的方向(我的google-fu正在努力寻找解决方案)，将不胜感激.

If anyone able to break this down into smaller logical steps or point me in the direction of some solid code to read (my google-fu is struggling to find solutions) that would be greatly appreciated.

谢谢您的时间！

推荐答案

这可以表述为多重约束背包问题(也称为多维背包问题)，其形式如下:

This can be formulated as a multiply constrained knapsack problem (also known as multidimensional knapsack problem) as follows.

目标函数和第一维与您当前的公式(即权重之和)相同.

The objective function and the first dimension remain the same as in your current formulation (i.e. the sum of weights).

第二维随后可用于约束所选项目的数量.使用维基百科符号:

The second dimension can then be used to constrain the number of selected items. Using Wikipedia notation:

对于所有 i ，
• w _2，i = 1；
• W ₂ =允许选择的项目数限制(在您的示例中为5).

以下是一些参考资料:

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

• 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

这篇关于背包数量限制的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！