使用 python，找到总和尽可能接近另一个数字的组合
Using python, find combinations of numbers whose sum is as close as possible to another
问题：
我需要在 array2 中找到三个数字，它们相加或尽可能接近 array3 中的每个数字（必须是三个数字）。
打印array2
array2中的每个数字只能使用两次。
数据：我在一个列表和两个数组中有三组数据。第一个列表是名称，第二个数组是数字，第三个数组是目标。 list1 和 array2 的长度相同（55），但 array3 不同。
list1 = ['ab', 'ac', 'ad', 'ae', 'af', 'ag', 'ah', 'ai', 'aj', 'ak',
'bc', 'bd', 'be', 'bf', 'bg', 'bh', 'bi', 'bj', 'bk', 'cd', 'ce',
'cf', 'cg', 'ch', 'ci', 'cj', 'ck', 'de', 'df', 'dg', 'dh', 'di',
'dj', 'dk', 'ef', 'eg', 'eh', 'ei', 'ej', 'ek', 'fg', 'fh', 'fi',
'fj', 'fk', 'gh', 'gi', 'gj', 'gk', 'hi', 'hj', 'hk', 'ij', 'ik',
'jk']
array2 = [39, 6, 29, 38, 2, 34, 7, 6, 2, 3, 37, 13, 20, 18, 4, 14,
28, 2, 20, 25, 13, 38, 32, 28, 9, 7, 14, 11, 31, 29, 29, 39, 9, 35,
14, 34, 23, 31, 11, 2, 37, 19, 18, 6, 5, 12, 6, 33, 30, 22, 38, 37,
13, 31, 40]
array3 = [80, 74, 84, 89, 89, 78, 79, 85, 81, 89, 75, 86, 76, 71,
82, 79, 75, 78, 83, 89]
我要查找的结果是：
对于 array3 中的 80，使用 39+38+3，即来自 list1 的 'ab'、'ae'、'ak'。
对于 array3 中的 74，使用 39+32+2，即来自 list1
的 'ab'、'cg'、'ek'
等等。
我正在尝试使用 python3.x 找到解决此问题的 pythonic 方法。我研究了 itertools.combinations/permutations 和背包问题。背包问题最接近解决这个问题，但评估两个值以获得针对目标的最佳解决方案，而我只需要一个。
我不是在找人为我编写代码（如果你愿意，我不会阻止你），而是在寻找比我更有经验的人来为我指明解决这个问题的正确方向。
这假设 array2 中的每个元素（具有不同的索引）仅使用一次（您可以扩展到元素重复），并且您不关心使用哪三个元素：
# target is the desired number from array3
def triplet_sum(list1, array2, target):
n = len(array2)
a = [(i, array2[i]) for i in range(n)]
a.sort(key=lambda x: x[1])
j = 1
i = j-1
k = j+1
best_sum = sys.maxsize
best_answer = None
while j < n:
while i >= 0 and k < n:
x = a[i][1]
y = a[j][1]
z = a[k][1]
S = x + y + z
candidate = [(x, list1[a[i][0]]), (y, list1[a[j][0]]), (z, list1[a[k][0]])]
if S == target:
return candidate
elif S > target:
i -= 1
else:
k += 1
if abs(target - best_sum) > abs(target - S):
best_sum = S
best_answer = candidate
j += 1
i = j-1
k = j+1
return best_answer
示例输出：
# Closest match
triplet_sum(list1, array2, 5)
[(2, 'af'), (2, 'aj'), (2, 'bj')]
# An exact match
triplet_sum(list1, array2, 80)
[(20, 'be'), (20, 'bk'), (40, 'jk')]
我只是将我的中间选择 j 沿排序列表 a 移动，如果 S 太高，则总是向左移动 i，并且到如果 S 太低，则使用 k。 O(n^2) 复杂度一目了然。
以下算法在 array2 中所有三元组的巨大 space 中为 array3 中的所有目标搜索 e 解：
list1 = ['ab', 'ac', 'ad', 'ae', 'af', 'ag', 'ah', 'ai', 'aj', 'ak', 'bc', 'bd', 'be', 'bf', 'bg', 'bh', 'bi', 'bj', 'bk', 'cd', 'ce', 'cf', 'cg', 'ch', 'ci', 'cj', 'ck', 'de', 'df', 'dg', 'dh', 'di', 'dj', 'dk', 'ef', 'eg', 'eh', 'ei', 'ej', 'ek', 'fg', 'fh', 'fi', 'fj', 'fk', 'gh', 'gi', 'gj', 'gk', 'hi', 'hj', 'hk', 'ij', 'ik', 'jk']
array2 = [39, 6, 29, 38, 2, 34, 7, 6, 2, 3, 37, 13, 20, 18, 4, 14, 28, 2, 20, 25, 13, 38, 32, 28, 9, 7, 14, 11, 31, 29, 29, 39, 9, 35, 14, 34, 23, 31, 11, 2, 37, 19, 18, 6, 5, 12, 6, 33, 30, 22, 38, 37, 13, 31, 40]
array3 = [80, 74, 84, 89, 89, 78, 79, 85, 81, 89, 75, 86, 76, 71, 82, 79, 75, 78, 83, 89]
import itertools
import numpy as np
import heapq
import copy
list1 = np.array(list1, dtype=str)
array2 = np.array(array2, dtype=int)
array3 = np.array(array3, dtype=int)
m, n = len(array2), len(array3)
combs = [[] for __ in range(n)]
maxuses = 2
combinations = set(map(tuple, itertools.combinations(list(range(m))*maxuses, 3)))
print(f'searching in {len(combinations)}! space')
def dist(a, b):
return abs(a - b)
for i, target in enumerate(array3):
for comb in map(list, combinations):
combs[i].append((dist(target, sum(array2[comb])), comb))
combs[i].sort(key=lambda item: item[0])
tested = set()
cost = 0
locs = [0]*n
used = {i: [] for i in range(m)}
for i in range(n):
for value in combs[i][0][1]:
used[value].append(i)
cost += combs[i][0][0]
def priority(values):
return (np.array(list(map(len, values)))**2).sum()
minheap = [(cost, priority(used.values()), locs, used)]
count = 0
while minheap:
cost, __, locs, used = heapq.heappop(minheap)
count += 1
print(f'tested {count}, best cost {cost}, heap size {len(minheap)}')
for key in used:
if len(used[key]) > maxuses:
loc1 = used[key][-1]
loc2 = next(itertools.islice(filter(lambda x: x != loc1, used[key]), 0, None))
print(f'value at {key} is used by {len(used[key])} combinations')
# print(key, used[key])
# print(loc1, combs[loc1][locs[loc1]][1])
# print(loc2, combs[loc2][locs[loc2]][1])
for value in combs[loc1][locs[loc1]][1]:
used[value].remove(loc1)
for value in combs[loc2][locs[loc2]][1]:
used[value].remove(loc2)
if loc1 < len(combinations)-1:
cost1 = cost
locs1 = list(locs)
used1 = copy.deepcopy(used)
cost1 -= combs[loc1][locs[loc1]][0]
locs1[loc1] += 1
cost1 += combs[loc1][locs[loc1]][0]
for value in combs[loc1][locs1[loc1]][1]:
used1[value].append(loc1)
for value in combs[loc2][locs1[loc2]][1]:
used1[value].append(loc2)
if tuple(locs1) not in tested:
tested.add(tuple(locs1))
heapq.heappush(minheap, (cost1, priority(used1.values()), locs1, used1))
if loc2 < len(combinations)-1:
cost2 = cost
locs2 = list(locs)
used2 = copy.deepcopy(used)
cost2 -= combs[loc2][locs2[loc2]][0]
locs2[loc2] += 1
cost2 += combs[loc2][locs2[loc2]][0]
for value in combs[loc1][locs2[loc1]][1]:
used2[value].append(loc1)
for value in combs[loc2][locs2[loc2]][1]:
used2[value].append(loc2)
if tuple(locs2) not in tested:
tested.add(tuple(locs2))
heapq.heappush(minheap, (cost2, priority(used2.values()), locs2, used2))
break
else:
print(f'found a solution with {cost} cost:')
print(locs)
for i , target in enumerate(array3):
print(f'{target}\t~=\t ', end='')
print(*array2[combs[i][locs[i]][1]], sep='+', end=' ')
print('\t(', end='')
print(*list1[combs[i][locs[i]][1]], sep=', ', end='')
print(')')
exit()
它将return（其中之一）最小化成本的三元组组合，并且最多只使用array2中的每个数字两次。
因为你没有指定最佳解决方案的标准，所以我假设三元组之和与其目标之间的绝对差值, 但您可以在 dist.
中更改它
您的示例运行速度非常快（<10 秒），但我保证它会这么快，您可能需要一些随机化。但这是您示例的一种解决方案：
80 ~= 28+23+29 (ch, eh, dg)
74 ~= 29+39+6 (dg, di, ai)
84 ~= 13+33+38 (ij, gj, hj)
89 ~= 37+39+13 (bc, di, ij)
89 ~= 30+40+19 (gk, jk, fh)
78 ~= 7+40+31 (ah, jk, ei)
79 ~= 31+18+30 (ei, fi, gk)
85 ~= 13+37+35 (ce, fg, dk)
81 ~= 18+32+31 (bf, cg, df)
89 ~= 34+20+35 (eg, be, dk)
75 ~= 13+28+34 (bd, bi, ag)
86 ~= 18+39+29 (bf, ab, dh)
76 ~= 29+38+9 (ad, hj, dj)
71 ~= 14+37+20 (bh, bc, be)
82 ~= 29+20+33 (dh, bk, gj)
79 ~= 14+37+28 (ef, hk, ch)
75 ~= 28+9+38 (bi, ci, ae)
78 ~= 34+38+6 (eg, cf, gi)
83 ~= 29+31+23 (ad, df, eh)
89 ~= 37+38+14 (hk, cf, ef)
问题：
我需要在 array2 中找到三个数字，它们相加或尽可能接近 array3 中的每个数字（必须是三个数字）。
打印array2
中使用的每个数字的list1中对应的索引
array2中的每个数字只能使用两次。
数据：我在一个列表和两个数组中有三组数据。第一个列表是名称，第二个数组是数字，第三个数组是目标。 list1 和 array2 的长度相同（55），但 array3 不同。
list1 = ['ab', 'ac', 'ad', 'ae', 'af', 'ag', 'ah', 'ai', 'aj', 'ak',
'bc', 'bd', 'be', 'bf', 'bg', 'bh', 'bi', 'bj', 'bk', 'cd', 'ce',
'cf', 'cg', 'ch', 'ci', 'cj', 'ck', 'de', 'df', 'dg', 'dh', 'di',
'dj', 'dk', 'ef', 'eg', 'eh', 'ei', 'ej', 'ek', 'fg', 'fh', 'fi',
'fj', 'fk', 'gh', 'gi', 'gj', 'gk', 'hi', 'hj', 'hk', 'ij', 'ik',
'jk']
array2 = [39, 6, 29, 38, 2, 34, 7, 6, 2, 3, 37, 13, 20, 18, 4, 14,
28, 2, 20, 25, 13, 38, 32, 28, 9, 7, 14, 11, 31, 29, 29, 39, 9, 35,
14, 34, 23, 31, 11, 2, 37, 19, 18, 6, 5, 12, 6, 33, 30, 22, 38, 37,
13, 31, 40]
array3 = [80, 74, 84, 89, 89, 78, 79, 85, 81, 89, 75, 86, 76, 71,
82, 79, 75, 78, 83, 89]
我要查找的结果是：
对于 array3 中的 80，使用 39+38+3，即来自 list1 的 'ab'、'ae'、'ak'。
对于 array3 中的 74，使用 39+32+2，即来自 list1
的 'ab'、'cg'、'ek'等等。
我正在尝试使用 python3.x 找到解决此问题的 pythonic 方法。我研究了 itertools.combinations/permutations 和背包问题。背包问题最接近解决这个问题，但评估两个值以获得针对目标的最佳解决方案，而我只需要一个。 我不是在找人为我编写代码（如果你愿意，我不会阻止你），而是在寻找比我更有经验的人来为我指明解决这个问题的正确方向。
这假设 array2 中的每个元素（具有不同的索引）仅使用一次（您可以扩展到元素重复），并且您不关心使用哪三个元素：
# target is the desired number from array3
def triplet_sum(list1, array2, target):
n = len(array2)
a = [(i, array2[i]) for i in range(n)]
a.sort(key=lambda x: x[1])
j = 1
i = j-1
k = j+1
best_sum = sys.maxsize
best_answer = None
while j < n:
while i >= 0 and k < n:
x = a[i][1]
y = a[j][1]
z = a[k][1]
S = x + y + z
candidate = [(x, list1[a[i][0]]), (y, list1[a[j][0]]), (z, list1[a[k][0]])]
if S == target:
return candidate
elif S > target:
i -= 1
else:
k += 1
if abs(target - best_sum) > abs(target - S):
best_sum = S
best_answer = candidate
j += 1
i = j-1
k = j+1
return best_answer
示例输出：
# Closest match
triplet_sum(list1, array2, 5)
[(2, 'af'), (2, 'aj'), (2, 'bj')]
# An exact match
triplet_sum(list1, array2, 80)
[(20, 'be'), (20, 'bk'), (40, 'jk')]
我只是将我的中间选择 j 沿排序列表 a 移动，如果 S 太高，则总是向左移动 i，并且到如果 S 太低，则使用 k。 O(n^2) 复杂度一目了然。
以下算法在 array2 中所有三元组的巨大 space 中为 array3 中的所有目标搜索 e 解：
list1 = ['ab', 'ac', 'ad', 'ae', 'af', 'ag', 'ah', 'ai', 'aj', 'ak', 'bc', 'bd', 'be', 'bf', 'bg', 'bh', 'bi', 'bj', 'bk', 'cd', 'ce', 'cf', 'cg', 'ch', 'ci', 'cj', 'ck', 'de', 'df', 'dg', 'dh', 'di', 'dj', 'dk', 'ef', 'eg', 'eh', 'ei', 'ej', 'ek', 'fg', 'fh', 'fi', 'fj', 'fk', 'gh', 'gi', 'gj', 'gk', 'hi', 'hj', 'hk', 'ij', 'ik', 'jk']
array2 = [39, 6, 29, 38, 2, 34, 7, 6, 2, 3, 37, 13, 20, 18, 4, 14, 28, 2, 20, 25, 13, 38, 32, 28, 9, 7, 14, 11, 31, 29, 29, 39, 9, 35, 14, 34, 23, 31, 11, 2, 37, 19, 18, 6, 5, 12, 6, 33, 30, 22, 38, 37, 13, 31, 40]
array3 = [80, 74, 84, 89, 89, 78, 79, 85, 81, 89, 75, 86, 76, 71, 82, 79, 75, 78, 83, 89]
import itertools
import numpy as np
import heapq
import copy
list1 = np.array(list1, dtype=str)
array2 = np.array(array2, dtype=int)
array3 = np.array(array3, dtype=int)
m, n = len(array2), len(array3)
combs = [[] for __ in range(n)]
maxuses = 2
combinations = set(map(tuple, itertools.combinations(list(range(m))*maxuses, 3)))
print(f'searching in {len(combinations)}! space')
def dist(a, b):
return abs(a - b)
for i, target in enumerate(array3):
for comb in map(list, combinations):
combs[i].append((dist(target, sum(array2[comb])), comb))
combs[i].sort(key=lambda item: item[0])
tested = set()
cost = 0
locs = [0]*n
used = {i: [] for i in range(m)}
for i in range(n):
for value in combs[i][0][1]:
used[value].append(i)
cost += combs[i][0][0]
def priority(values):
return (np.array(list(map(len, values)))**2).sum()
minheap = [(cost, priority(used.values()), locs, used)]
count = 0
while minheap:
cost, __, locs, used = heapq.heappop(minheap)
count += 1
print(f'tested {count}, best cost {cost}, heap size {len(minheap)}')
for key in used:
if len(used[key]) > maxuses:
loc1 = used[key][-1]
loc2 = next(itertools.islice(filter(lambda x: x != loc1, used[key]), 0, None))
print(f'value at {key} is used by {len(used[key])} combinations')
# print(key, used[key])
# print(loc1, combs[loc1][locs[loc1]][1])
# print(loc2, combs[loc2][locs[loc2]][1])
for value in combs[loc1][locs[loc1]][1]:
used[value].remove(loc1)
for value in combs[loc2][locs[loc2]][1]:
used[value].remove(loc2)
if loc1 < len(combinations)-1:
cost1 = cost
locs1 = list(locs)
used1 = copy.deepcopy(used)
cost1 -= combs[loc1][locs[loc1]][0]
locs1[loc1] += 1
cost1 += combs[loc1][locs[loc1]][0]
for value in combs[loc1][locs1[loc1]][1]:
used1[value].append(loc1)
for value in combs[loc2][locs1[loc2]][1]:
used1[value].append(loc2)
if tuple(locs1) not in tested:
tested.add(tuple(locs1))
heapq.heappush(minheap, (cost1, priority(used1.values()), locs1, used1))
if loc2 < len(combinations)-1:
cost2 = cost
locs2 = list(locs)
used2 = copy.deepcopy(used)
cost2 -= combs[loc2][locs2[loc2]][0]
locs2[loc2] += 1
cost2 += combs[loc2][locs2[loc2]][0]
for value in combs[loc1][locs2[loc1]][1]:
used2[value].append(loc1)
for value in combs[loc2][locs2[loc2]][1]:
used2[value].append(loc2)
if tuple(locs2) not in tested:
tested.add(tuple(locs2))
heapq.heappush(minheap, (cost2, priority(used2.values()), locs2, used2))
break
else:
print(f'found a solution with {cost} cost:')
print(locs)
for i , target in enumerate(array3):
print(f'{target}\t~=\t ', end='')
print(*array2[combs[i][locs[i]][1]], sep='+', end=' ')
print('\t(', end='')
print(*list1[combs[i][locs[i]][1]], sep=', ', end='')
print(')')
exit()
它将return（其中之一）最小化成本的三元组组合，并且最多只使用array2中的每个数字两次。
因为你没有指定最佳解决方案的标准，所以我假设三元组之和与其目标之间的绝对差值, 但您可以在 dist.
您的示例运行速度非常快（<10 秒），但我保证它会这么快，您可能需要一些随机化。但这是您示例的一种解决方案：
80 ~= 28+23+29 (ch, eh, dg)
74 ~= 29+39+6 (dg, di, ai)
84 ~= 13+33+38 (ij, gj, hj)
89 ~= 37+39+13 (bc, di, ij)
89 ~= 30+40+19 (gk, jk, fh)
78 ~= 7+40+31 (ah, jk, ei)
79 ~= 31+18+30 (ei, fi, gk)
85 ~= 13+37+35 (ce, fg, dk)
81 ~= 18+32+31 (bf, cg, df)
89 ~= 34+20+35 (eg, be, dk)
75 ~= 13+28+34 (bd, bi, ag)
86 ~= 18+39+29 (bf, ab, dh)
76 ~= 29+38+9 (ad, hj, dj)
71 ~= 14+37+20 (bh, bc, be)
82 ~= 29+20+33 (dh, bk, gj)
79 ~= 14+37+28 (ef, hk, ch)
75 ~= 28+9+38 (bi, ci, ae)
78 ~= 34+38+6 (eg, cf, gi)
83 ~= 29+31+23 (ad, df, eh)
89 ~= 37+38+14 (hk, cf, ef)