背包问题，但允许过度填充 [英] Knapsack prob, but allow over-filling

问题描述

假设我有5个项目(名称，大小，值)，如下所示:

Lets say I have 5 items (name, size, value) as follows:

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

我必须获得最接近的匹配，总大小为150(每个项目只能添加一次).

and I have to get the closest match to a total size of 150 (each item can only be added once).

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

This is very similar to the knapsack problem, but not quite since in this case my preferable solution would be ITEM01, ITEM04 giving a total size of 151 (the knapsack problem would stop me going over size = 150 and hence give ITEM01, ITEM02 and ITEM03 with a total size of 148).

这个问题有名字吗? (是否仍然是combinatorial optimisation)?我正在寻找python解决方案，但是如果我知道我要寻找的名称，它将对您有帮助.

Does this problem have a name? (Is it still combinatorial optimisation)? I'm looking for a python solution, but it would help if I knew the name of what I am looking for.

推荐答案

您可以尝试使用动态编程来做到这一点.

You can try to do it using dynamic programming.

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

Let dp[k] be equal to a list of items, with the sum of size equal to k. Initially d[0] = [] and dp[k] = None for k > 0. The size of the list may be bounded by the sum of sizes of all elements, let's call it S.

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

What the algorithm does is for each item it goes from i = S down to i = 0 and it checks if dp[i] != None, which means we know we are able to select items with sum of sizes equal to i. These items are on the list dp[i]. Let's observe that we can add the current item to that list and have a set of items with sum equal to i + item.size. So we assign dp[i + item.size] = dp[i] + [item]. Having processed all items we just have to start at the desired sum of sizes and go both directions to find the closest match.

代码:

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是所有商品的最小尺寸.

However the complexity of this solution is O(n*S) where n is the number of items and S is the sum of sizes, so it may be too slow for some purposes. What can be improved in this solution is the S constant. For example you can set S to 2 * desired_sum because we have guarantee that we can take a set of items with sum of sizes in [0, 2 * desired_sum] (possibly an empty set with sum 0). If you want to take at least one item you can take S = max(min_item_size, 2 * desired_sum - min_item_size) where min_item_size is the minimum of sizes of all items.

编辑:

哦，当两个组合均与desired_size接近时，您还希望获得最大化的价值.然后，您必须对代码进行一些替换，以保持每种大小总和的最佳组合.

Oh, you also wanted get maximise value when two combinations are equally close to desired_size. Then you have to alternate the code a bit to keep the best combinations for each sum of sizes.

即:

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]])
    ):

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

(a bit ugly, but I don't know how to break lines to make it look better)

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

Of course you can keep these sums to avoid calculating them each time.

这篇关于背包问题，但允许过度填充的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！