优化问题在Python(使用二进制数组)可能的解决方案

Question

我有一个问题，我有一个大二进制numpy数组(1000,2000)。总体思路是，数组的列表示从0到2000的时间，每行表示一个任务。数组中的每一个0代表失败，每一个1代表成功。

我需要做的是从1000个可用的任务中选择150个任务(行轴)，并在唯一列上最大化总成功(15)。它不必是连续的，我们只是在寻找每个时间段的最大成功(只需要一个成功，任何额外的是无关紧要的)。我想选择最好的"篮子"。在150个任务中。子数组行可以取自1000行初始行中的任何位置。我想要一个最佳的"篮子"。从时间跨度来看，150个最成功的任务(列)。(为更加清晰而编辑)

数组的基本示例:

array([[0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0],
[0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1],
[0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0],
[1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0],
[1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0],
[1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0]])

我已经成功地创建了一个蒙特卡罗模拟，使用NumPy中随机生成的任务篮，然后遍历数组和求和。您可以想象，这需要一些时间，并且考虑到大量潜在的组合，这是低效的。有人能给我指出一个算法或方法来解决这个问题吗?

Answer 1

试试这个:

n = 150
row_sums = np.sum(x, axis=1)
top_n_row_sums = np.argsort(row_sums)[-n:]
max_successes = x[top_n_row_sums]

取每一行的和，获取n和的最高值的索引，并用这些行索引索引到x。

注意，行最终将按照它们在各列上的和的升序排序。如果希望按正常顺序排列(按索引升序排列)，请使用以下命令:

max_successes = x[sorted(top_n_row_sums)]

Answer 2

为什么不直接计算每行成功次数的总和，然后您就可以轻松地选择前150个值。