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

Question

我正在尝试解决一个优化问题，该问题包括寻找子集求和问题的最佳解决方案，但是，我们需要找到一个解决方案，其中每列的总和最接近每列的唯一数字.另一个约束是它应该是 table 中只有 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

请注意这是一个示例 table，其中包含示例值

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

解释如何操作的 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 感兴趣，但需要计算其他值）。
外层字典的key是"Parameter 1"的和；
第一个嵌套字典的key是"Parameter 2"的总和；
第二个嵌套字典的key是"Parameter 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，但我认为它不适用于任何假设的距离。
可以通过一些额外的假设来修剪可能性树。

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

How to find N numbers whose sum is closest to K , but over multiple columns?

python

algorithm

optimization

knapsack-problem

subset-sum