我试图解决一个优化问题，它包括寻找一个子集和问题的最优解，但是，我们需要找到一个解决方案，其中每一列的和最接近每一列的唯一数。另一个限制是它应该是表中只有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
我只想找三排，
参数1的和最接近30
参数2之和最接近60
参数3之和最接近70
请注意，这是一个带有示例值的示例表
这是一个家庭作业问题，我已经花了很多时间试图解决它我知道这是一个优化问题，主要是背包问题的边缘情况，我应该使用动态规划来解决它，但我不知道如何在多个约束条件下而不是一个约束条件下这样做。我已经研究过多维背包了，但是不知道怎么做。
一本介绍如何做的笔记本会很有帮助
最佳答案
你说的是背包问题，但有几个特点：
你不想找到一个确切的和，但最接近一个值的结果；
问题是多层面的；
这个数字不能保证是正的；
你没有提供距离。
我认为你最好的办法是枚举大小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的列表：dict的索引是使用的行数（我们对K感兴趣，但需要计算其他值）。外部指令的关键是“参数1”的和；
第一个嵌套dict的键是“参数2”的和；
第二个嵌套dict的键是“参数3”的和；
值是已使用行的列表。
（我没有使用四维数组，因为它本来是非常稀疏的。）
一个小技巧：我用目标初始化
list_by_triplet_by_k如果我们有0排，我们是AT-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，但我不认为它适用于任何假设距离。
有了一些额外的假设，就有可能修剪出可能性之树。
关于python - 如何找到总和最接近K但在多列上的N个数字？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/57243498/