python - 如何找到 N 个数字，其总和最接近 K 但在多个列上？

Question

我正在尝试解决一个优化问题，该问题包括寻找子集求和问题的最佳解决方案，但是，我们需要找到一个解决方案，其中每列的总和最接近每列的唯一数字。另一个约束是它应该是表中只有 45 行的总和。

我已经尝试过使用 Bruteforce，但它只会耗尽系统资源。根据我对这个问题的理解，这是背包问题的一个子集，称为子集和问题，但我想在多个列上执行此操作。

为了更好的说明问题

Label | Weight | Parameter 1 | Parameter 2 | Parameter 3
Item1 |   12   |     13      |    91       |      24
Item2 |   76   |     12      |    10       |      14
Item3 |   43   |     11      |    34       |      35
Item4 |   23   |     16      |    11       |      10
Item5 |   23   |     40      |    14       |      12
Item6 |   83   |     70      |    11       |      40
Item7 |   22   |     11      |    41       |      20

我想找到仅 3 行， 参数 1 的总和最接近到 30
参数 2 的总和最接近 60 参数 3 的总和最接近70

请注意这是一个包含示例值的示例表

这是一道家庭作业题，我已经花了很多时间来解决它。我知道这是一个优化问题，主要是背包问题的边缘情况，我应该使用动态规划来解决它，但我无法弄清楚如何针对多个约束而不是一个约束来做到这一点。我已经研究过多维背包，但不知道该怎么做。

解释如何做的 Jupyter notebook 会很有帮助

Answer 1

你说的是背包问题，但有一些特殊之处:

• 您不想找到一个精确的总和，而是最接近某个值的结果；
• 问题是多方面的；
• 不保证数字是正数；
• 您没有提供距离。

我认为最好的办法是枚举大小为 K 的子集并选择最接近的总和。这是蛮力，但动态规划可能有助于输出子集并计算总和。

正如评论中指出的，您首先必须定义closest 的含义。也就是说，定义一个距离。例如，欧氏距离很常见:

def d(p1, p2, p3):
    return p1*p1 + p2*p2 + p3*p3

让我们从文件中提取数据，更准确地说，是最后三个值(参数 1、2、3)和行的索引:

DATA = """Label | Weight | Parameter 1 | Parameter 2 | Parameter 3
Item1 |   12   |     13      |    91       |      24
Item2 |   76   |     12      |    10       |      14
Item3 |   43   |     11      |    34       |      35
Item4 |   23   |     16      |    11       |      10
Item5 |   23   |     40      |    14       |      12
Item6 |   83   |     70      |    11       |      40
Item7 |   22   |     11      |    41       |      20"""

import io
import csv

f = io.StringIO(DATA)
reader = csv.reader(f, delimiter='|')
next(reader) # skip the header

L = [tuple([int(v) for v in row[-3:]] + [i]) for i, row in enumerate(reader)]
# [(13, 91, 24, 0), (12, 10, 14, 1), (11, 34, 35, 2), (16, 11, 10, 3), (40, 14, 12, 4), (70, 11, 40, 5), (11, 41, 20, 6)]

现在，设置行数 K 和目标 T(三元组)

N = len(L)
K = 3
T = (30, 60, 70)

它是动态规划，因此我们需要存储中间结果。 list_by_triplet_by_k 是嵌套字典的列表:

• dict 的索引是使用的行数(我们对K 感兴趣，但需要计算其他值)。
• 外层dict的key为“参数1”之和；
• 第一个嵌套dict的key为“参数2”之和；
• 第二个嵌套dict的key为“参数3”之和；
• 该值是已用行的列表。

(我没有使用 4 维数组，因为它会非常稀疏。)

小技巧:我用目标初始化 list_by_triplet_by_k。如果我们有 0 行，我们在 -T。

list_by_triplet_by_k = [{} for _ in range(N)]
list_by_triplet_by_k[0] = {-T[0]: {-T[1]: {-T[2]: [(-T[0], -T[1], -T[2], "target")]}}}

让我们构建子集。基本上，我们使用动态规划构建了一个由 K+1 树组成的森林:

best = None
ret = []
for a, b, c, i in L:
    for k in range(0, K):
        list_by_triplet = list_by_triplet_by_k[k]
        for u in list_by_triplet.keys():
            for v in list_by_triplet[u].keys():
                for w in list_by_triplet[u][v]:
                    if (a, b, c, i) not in list_by_triplet[u][v][w]: # 0/1
                        list_by_triplet_by_k[k+1].setdefault(a+u, {}).setdefault(b+v, {})[c+w] = list_by_triplet[u][v][w] + [(a, b, c, i)]

    # compute the best match on the fly at the end (not a very useful optimization, but why not?):
    list_by_triplet = list_by_triplet_by_k[K-1]
    for u in list_by_triplet.keys():
        for v in list_by_triplet[u].keys():
            for w in list_by_triplet[u][v]:
                if (a, b, c, i) not in list_by_triplet[u][v][w]: # 0/1
                    cur = d(u+a, v+b, w+c)
                    if best is None or cur < best:
                        best = cur
                        ret = list_by_triplet[u][v][w] + [(a, b, c, i)]

也许有一个技巧可以通过设计避免重复，我不知道:我只是测试了该元素是否已经在列表中。

结果:

print (best, ret)
# 227 [(-30, -60, -70, 'target'), (12, 10, 14, 1), (11, 34, 35, 2), (16, 11, 10, 3)]

备注:

• 参见 https://cs.stackexchange.com/a/43662以获取信息，但我认为它不适用于任何假设的距离。
• 可以通过一些额外的假设来修剪可能性树。