设 A 、 B 和 C 是三个数组，每个数组包含 N 编号:
A = a[0], a[1], a[2], ..., a[N-1]
B = b[0], b[1], b[2], ..., b[N-1]
C = c[0], c[1], c[3], ..., c[N-1]
k < N 中选择最好的 A 元素，从 k < N 中选择最好的 B 元素，以便最大化它们的总和。有趣的转折是:如果元素 i 是从 A 和 B (其中 i 中的 {0, ..., N-1} 是索引)中选择的，那么它们将贡献 a[i] + b[i] where c[i] 而不是这些元素提供 c[i] >= a[i] + b[i] 。乍一看，这对我来说似乎很简单，但我想得越多，它就越复杂。
我最终是在寻找 Python 的实现，但在这个阶段，我只是想了解什么是有效的算法。
例子
为了澄清，算法的输入是 3 个
N x 1 数组 A 、 B 和 C 以及 k 的整数值。预期输出是两个 k x 1 索引列表，定义来自 A 和 B (和 C )的元素的值最大化组合。例如，假设
k = 2 、 N = 4 和 let A = a[0], a[1], a[2], a[3] = 3, 1, 1, 0
B = b[0], b[1], b[2], b[3] = 1, 3, 0, 1
C = c[0], c[1], c[2], c[3] = 4, 4, 3, 2
i = 0, 2 是从 A 中选择的，而元素 j = 1, 3 是从 B 中选择的，那么总值将为 a[0] + a[2] + b[1] + b[3] = 8 。另一方面，如果元素
i = 0, 1 和 j = 0, 1 将从 A 和 B 中选择，那么特殊的扭曲适用:不是产生 a[0] + a[1] + b[0] + b[1] ，而是由 c[0] + c[1] = 8 给出总值。在此示例中，使总值最大化的元素组合由来自
i = 0, 2 的 A 和来自 j = 1, 2 的元素 B 给出。这产生了 a[0] + b[1] + c[2] = 9 的总值，可以验证的比任何其他组合都多。答案对比
这是 3 个提交的解决方案的快速比较。首先，我检查了所有这些，它们都给出了预期的结果。作为旁注，它们都不需要
C 的元素比 A 和 B 中相应元素的总和稍大，所以我在性能评估中放弃了这个假设。这是我运行的内容:
import numpy as np
from utils import tic, toc # simple wrapper to time.perf_counter()
k, N = 10, 1000
A = list(np.random.random_sample([N]))
B = list(np.random.random_sample([N]))
C = list(np.random.random_sample([N]))
tic()
print(optimal_choices(k, A, B, C)) # solution by btilly
toc()
tic()
print(maxPicks(A.copy(), B.copy(), C.copy(), k)) # solution by Eric T-M
toc()
tic()
print(maxSum(A, B, C, k)) # solution by Alain T.
toc()
k 和 N 的各种组合。只要 N 很小，@btilly 的算法似乎就可以在 k 中很好地扩展。 @Alain-T. 的算法正好相反，当 k 相对于 N 大时效果很好。总体而言，@Eric-T-M 的算法效果最好，在 k 和 N 中都能很好地扩展。小问题:k = 10 和 N = 500
小 k，大 N:k = 10 和 N = 1000
大 k、小 N:k = 80 和 N = 100
中等问题:k = 50 和 N = 1000
大问题 1:k = 10 且 N = 1_000_000
大问题 2:k = 1_000 和 N = 100_000
(对于基准测试，我删除了 Alain T. 代码中的排序，以使其具有可比性。)
最佳答案
试试这个。这需要 O(N^2) 时间，而且相当简单。
def maxPicks(A,B,C,k):
# returns the tuple (list of entries picked in A, list of entries picked in B, total value)
# BASE CASE
if k == 0:
return ([], [], 0)
aMax = max(A)
bMax = max(B)
cMax = max(C)
if (aMax + bMax) > cMax:
aIdx = A.index(aMax)
bIdx = B.index(bMax)
B[aIdx] = C[aIdx] - A[aIdx]
A[aIdx] = -2
C[aIdx] = -1
A[bIdx] = C[bIdx] - B[bIdx]
B[bIdx] = -2
C[bIdx] = -1
nextPicks = maxPicks(A,B,C,k-1)
return (nextPicks[0] + [aIdx], nextPicks[1] + [bIdx], nextPicks[2] + aMax + bMax)
else:
cIdx = C.index(cMax)
A[cIdx] = -1
B[cIdx] = -1
C[cIdx] = -1
nextPicks = maxPicks(A,B,C,k-1)
return (nextPicks[0] + [cIdx], nextPicks[1] + [cIdx], nextPicks[2] + cMax)
基本情况应该是不言自明的。否则，我们会将
A 中所有条目的最大值和 B 中所有条目的最大值之和与 C 中所有条目的最大值进行比较。如果这个总和大于从 A 和 B 中选择这些条目是安全的，但在进行更多选择之前，我们需要将我们选择的条目以及它们在 C 中的相应条目设置为负值。作为旁注，我确实假设 A、B 和 C 中的所有值最初都是非负的，因此通过将它们设置为负，我们禁止我们的算法再次选择它们。如果这个假设是错误的，您可能希望将这些值设置为非常负的值以禁止重复选择。我们还看到，如果我们选择 A[i] ，那么 B[i] 的值现在是 C[i]-A[i] 的任何值，因为选择 B[i] 将使我们失去 A[i] 中的值，而如果我们选择 C[i] ，则 A[j] 中的值与条目 B[j] 相同。另一方面，如果
C 中的最大条目大于或等于 aMax+bMax 我们想要选择它(通过选择 A 和 B 中的相应条目，因为没有其他选择 A 和 B 或仅 C 中的条目会更有值(value)。此时我们知道我们不想重新选择 A[i],B[i] 或 C[i] 了，所以我们将它们设置为负数。
关于python - 从总值最高的 2 个数组中从 N 个数字中选择 k 个，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/66263919/