背包问题，但允许过度填充

Question

假设我有5个项目（名称，大小，值），如下：

("ITEM01", 100, 10000)
("ITEM02", 24, 576)
("ITEM03", 24, 576)
("ITEM04", 51, 2500)
("ITEM05", 155, 25)

而且我必须获得最接近的匹配，总大小为150（每个项目只能添加一次）。

这与背包问题非常相似，但不完全相同，因为在这种情况下，我的首选解决方案是ITEM01，ITEM04的总大小为151（背包问题会使我超过大小= 150，因此给出ITEM01，ITEM02和ITEM03，总大小为148）。

这个问题有名字吗？ （还是combinatorial optimisation）吗？我正在寻找python解决方案，但是如果我知道我要寻找的名称，这将有所帮助。

Answer 1

您可以尝试使用动态编程来实现。

让dp[k]等于项目列表，大小总和等于k。最初d[0] = []和dp[k] = None为k > 0。列表的大小可能受所有元素的大小之和限制，我们称其为S。

[算法对每个item所做的是，它从i = S下降到i = 0，并检查dp[i] != None是否成立，这意味着我们知道我们能够选择总和等于i的项目。这些项目在列表dp[i]上。让我们观察一下，我们可以将当前的item添加到该列表中，并具有一组总和等于i + item.size的项。因此，我们分配dp[i + item.size] = dp[i] + [item]。处理完所有项目后，我们只需要从所需的大小总和开始，然后双向进行查找即可找到最匹配的对象。

代码：

items = [("ITEM01", 100, 10000), ("ITEM02", 24, 576), \
    ("ITEM03", 24, 576), ("ITEM04", 51, 2500), ("ITEM05", 155, 25)]
S = sum([item[1] for item in items])
dp = [None for i in xrange(S + 1)]
dp[0] = []

for item in items:
    for i in xrange(S, -1, -1):
        if dp[i] is not None and i + item[1] <= S:
            dp[i + item[1]] = dp[i] + [item]

desired_sum = 150
i = j = desired_sum

while i >= 0 and j <= S:
    if dp[i] is not None:
        print dp[i]
        break
    elif dp[j] is not None:
        print dp[j]
        break
    else:
        i -= 1
        j += 1

输出：

[('ITEM01', 100, 10000), ('ITEM04', 51, 2500)]

然而，此解决方案的复杂度为O(n*S)，其中n是项数，S是大小之和，因此对于某些目的，它可能太慢。在该解决方案中可以改进的是S常数。例如，您可以将S设置为2 * desired_sum，因为我们保证可以获取一组总和为[0, 2 * desired_sum]的项目（可能为总和为0的空集）。如果要至少一件商品，可以拿S = max(min_item_size, 2 * desired_sum - min_item_size)，其中min_item_size是所有商品的最小尺寸。

编辑：

哦，当两个组合都同样接近desired_size时，您还希望获得最大化的值。然后，您必须稍微替换一下代码，以保持每种大小总和的最佳组合。

即：

if dp[i] is not None and i + item[1] <= S:

应该是：

if dp[i] is not None and i + item[1] <= S and \
    (
        dp[i + item[1]] is None
        or
        sum(set_item[2] for set_item in dp[i]) + item[2]
            > sum(set_item[2] for set_item in dp[i + item[1]])
    ):

（有点难看，但是我不知道如何换行以使其看起来更好）

当然，您可以保留这些总和以避免每次计算它们。

Answer 2

假设您有一个可以使用的背包求解器，并且有很多时间：

将每件物品的值设置为每件物品的重量，并解决容量为150的背包问题。这将使您的最大尺寸小于目标尺寸（本例中为148）。因此要考虑的最大大小为150 +（150-148）= 152

现在为150和152之间的每个整数再次求解。如果发现较小的差异（在您的示例中为151），请停止使用该值并使用原始项目值求解值。如果范围很大，您还可以尝试二进制搜索。

否则解决容量为148和152的原始背包问题，并选择具有最大价值的解决方案。

Answer 3

@ Spatial-SDE，您有什么可以分享的，因为我在这里遇到类似的问题。本质上，我正在寻找最小成本以得到准确的重量（或更高），并允许（多个）重复项。任何帮助或指示都将受到欢迎！

Knapsack problem with repeating components for lowest value, to fill (or slightly over) in Python。