问题是:
我需要在array2中找到三个数字相加,或者尽可能接近array3中的每个数字(必须是三个数字)。
从列表1打印array2中使用的每个数字的对应索引
array2中的每个数字只能使用两次。
数据:我在一个列表和两个数组中有三组数据。第一个列表是名称,第二个数组是number,第三个数组是targets。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]
我要找的结果是:
对于数组3中的80,使用39+38+3,即列表1中的“ab”、“ae”、“ak”。在
对于array3中的74,使用39+32+2,即列表1中的“ab”、“cg”、“ek”
等等。在
我试图找到一个Python式的方法来解决这个问题,使用python3.xitertools.组合/排列还有背包问题。背包问题是最接近于解决这个问题的,但是评估了两个值以获得针对目标的最佳解决方案,我只需要一个。 我不是在找人帮我写代码(如果你想的话,我不会阻止你),而是找一个比我更有经验的人来为我指出解决这个问题的正确方向。在
下面的算法在
array2
中所有三元组的巨大空间中搜索array3
中的所有目标的解:它将返回(其中一个)三胞胎组合,使成本最小化,并且最多只使用
array2
中的每个数字两次。在因为在没有精确解的情况下,您没有指定最佳解的标准,所以我假设三元组的和与其目标值之间的绝对差,但是您可以在
dist
中更改它。在对于您的示例,它的工作速度非常快(<;10s),但我保证它将与此一样快,而且您可能需要一些随机分组。但这是一个解决方案:
^{pr2}$这假设array2中的每个元素(具有不同的索引)只使用一次(可以扩展到元素repeats),并且不关心使用哪三个元素:
输出示例:
^{pr2}$我只是沿着排序列表}太低,则向右
a
移动中间选择j
,如果S
太高,总是向左i
,如果{k
。O(n^2)复杂性一目了然。在相关问题 更多 >
编程相关推荐