2

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

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

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

这与背包问题非常相似，但不完全相似，因为在这种情况下，我的首选解决方案是ITEM01，ITEM04总大小为 151（背包问题将阻止我超过 size = 150 并因此给出，ITEM01总大小为148)。ITEM02ITEM03

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

4

2 回答 2

2

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

让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]（可能是一个带有 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]])
    ):

（有点难看，但是不知道怎么打断线让它看起来更好看）

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

于 2013-03-20T11:52:10.157 回答
0

假设你有一个工作的背包求解器并且有很多时间：

将每个项目的值设置为每个项目的重量并解决容量为 150 的背包问题。这将使您的最大尺寸小于目标（在您的示例中为 148）。所以要考虑的最大尺寸是 150 + (150 - 148) = 152

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

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

于 2013-03-20T16:23:52.780 回答