algorithm - 当我想选择项目以尽可能满地填充容器时，它叫什么 - 我应该使用什么算法？

Question

我遇到的问题如下:

You are given item types of weight w1, w2, w3, .... wn; each item ofthese types is infinite in quantity.

You have a container capable of carrying weight W.

Find the combination(s) of items with greatest sum of weights thatwill fit in the container without exceeding the maximum weight W.

例如:

I have three types of items with weights:

• w = 5
• w = 10
• w = 20

And I have a container of Weight capacity:W = 25

Possible solutions would be:

• 5 items of w = 5, 0 items of w = 10, 0 items of w = 20;
• 1 item of w = 5, 0 items of w = 10, 1 item of w = 20

我能够使用动态规划方法解决问题；但是，我这里的问题是确定此类问题的名称以及用于解决该问题的算法。尽管进行了广泛的搜索，但我似乎无法触及它。

对我来说，它类似于装箱问题，只是箱子数量有限，元素数量无限，并且无法在多项式时间内解决。可能是元素重量 = 元素利润和每个元素无限数量的离散背包？

Answer 1

如果我理解正确，

For xi belongs to {0,1, ... infinity} (i = 1 to n)
Maximize summation(wixi) (i = 1 to n)
subject to:
summation (wixi) <= W

您可以使用整数线性规划求解器求解。

编辑:正如 Preston Guillot 所指出的，这是 背包问题 的一个特例，其中元素的 value 和 mass 是一样。