首先，谢谢你提出了一个好问题。我不经常练习numpy。而且，我没有太多在SE上发帖的经验，所以欢迎任何反馈，代码评论和与答案相关的意见。
这是一个试图找到一个最佳的解决方案，但我没有设法处理的复杂性。该算法应该，然而，给予你一个贪婪的解决方案，可能被证明是足够的。
Colab Notebook (Python code + Octave validation)

核心理念

注意：在运行时，我已经转置了矩阵。所以，问题中的列向量对应于算法中的行向量。
请注意，您可以一次将目标与一个向量相乘，有效地获得一个新目标，但其中包含一些0s。这些将永远不会更改，因此您可以通过删除这些行来过滤掉一些计算（列，在算法中）在进一步的计算中完全-从目标和矩阵。-然后你再次留下一个有效的目标（其中只有1s和-1）。
这是算法的基本思想。给定：

• n：需要拾取的向量数
• b：要检查的最佳向量数
• m：检查一个向量的矩阵运算的复杂性

执行指数复杂的O((n*m)^b)深度优先搜索，但通过减少目标/矩阵大小来降低更深层计算的复杂性，同时使用一些算法减少一些搜索路径。

使用的启发式方法

1.到目前为止达到的最好分数在每个递归步骤中都是已知的。计算一个乐观向量（将-1变成0），并检查仍然可以达到的分数。不要在分数无法超过的级别中搜索。
如果矩阵中最好的向量有1s和0s均匀分布，这是无用的。乐观得分太高了。然而，随着稀疏度的增加，它会变得更好。
1.忽略重复项。基本上，不检查同一层中的重复向量。因为我们减小了矩阵大小，所以在更深的递归级别中，重复项的可能性会增加。

关于启发式的进一步思考最有价值的是那些在开始时消除向量选择的方法。可能有一种方法可以找到比其他向量更差或相等的向量，关于它们对目标的影响。比如，如果v1与v2只相差一个额外的1，并且目标在该行中有一个-1，则v1比v2更差或等于v2。

问题是我们需要找到不止一个向量，而不能轻易丢弃其余的向量。如果我们有10个向量，每一个都比前一个更差或相等，我们仍然必须在开始时保留5个（以防它们仍然是最好的选择），然后在下一个递归级别中保留4个，在下面的递归级别中保留3个，等等。
也许有可能生成一棵树并将其传递到递归中？尽管如此，这并不能帮助削减开始时的搜索空间......也许只考虑差或相等链中的1或2个向量会有所帮助？这将探索更多样化的解决方案，但并不能保证它是更优的。

**警告：**注意例子中的MATRIX和TARGET都在int8中，如果你用它们做点积会溢出，虽然我认为算法中的所有操作都是在创建新的变量，所以不受影响。
验证码

# Given:
TARGET = np.random.choice([1, -1], size=60000).astype(np.int8)
MATRIX = np.random.randint(0, 2, size=(10000,60000), dtype=np.int8)

# Tunable - increase to search more vectors, at the cost of time.
# Performs better if the best vectors in the matrix are sparse
MAX_BRANCHES = 3   # can give more for sparser matrices

# Usage
score, picked_vectors_idx = pick_vectors(TARGET, MATRIX, 5)

# Function
def pick_vectors(init_target, init_matrix, vectors_left_to_pick: int, best_prev_result=float("-inf")):
    assert vectors_left_to_pick >= 1
    if init_target.shape == (0, ) or len(init_matrix.shape) <= 1 or init_matrix.shape[0] == 0 or init_matrix.shape[1] == 0:
        return float("inf"), None
    target = init_target.copy()
    matrix = init_matrix.copy()

    neg_matrix = np.multiply(target, matrix)
    neg_matrix_sum = neg_matrix.sum(axis=1)

    if vectors_left_to_pick == 1:
        picked_id = np.argmax(neg_matrix_sum)
        score = neg_matrix[picked_id].sum()
        return score, [picked_id]

    else:
        sort_order = np.argsort(neg_matrix_sum)[::-1]
        sorted_sums = neg_matrix_sum[sort_order]
        sorted_neg_matrix = neg_matrix[sort_order]
        sorted_matrix = matrix[sort_order]

        best_score = best_prev_result
        best_picked_vector_idx = None

        # Heuristic 1 (H1) - optimistic target.
        # Set a maximum score that can still be achieved
        optimistic_target = target.copy()
        optimistic_target[target == -1] = 0
        if optimistic_target.sum() <= best_score:
            # This check can be removed - the scores are too high at this point
            return float("-inf"), None

        # Heuristic 2 (H2) - ignore duplicates
        vecs_tried = set()

        # MAIN GOAL:   for picked_id, picked_vector in enumerate(sorted_matrix):
        for picked_id, picked_vector in enumerate(sorted_matrix[:MAX_BRANCHES]):
            # H2
            picked_tuple = tuple(picked_vector)
            if picked_tuple in vecs_tried:
                continue
            else:
                vecs_tried.add(picked_tuple)

            # Discard picked vector
            new_matrix = np.delete(sorted_matrix, picked_id, axis=0)
            
            # Discard matrix and target rows where vector is 0
            ones = np.argwhere(picked_vector == 1).squeeze()
            new_matrix = new_matrix[:, ones]
            new_target = target[ones]
            if len(new_matrix.shape) <= 1 or new_matrix.shape[0] == 0:
                return float("-inf"), None

            # H1: Do not compute if best score cannot be improved
            new_optimistic_target = optimistic_target[ones]
            optimistic_matrix = np.multiply(new_matrix, new_optimistic_target)
            optimistic_sums = optimistic_matrix.sum(axis=1)
            optimistic_viable_vector_idx = optimistic_sums > best_score
            if optimistic_sums.max() <= best_score:
                continue
            new_matrix = new_matrix[optimistic_viable_vector_idx]
         
            score, next_picked_vector_idx = pick_vectors(new_target, new_matrix, vectors_left_to_pick - 1, best_prev_result=best_score)
            
            if score <= best_score:
                continue

            # Convert idx of trimmed-down matrix into sorted matrix IDs
            for i, returned_id in enumerate(next_picked_vector_idx):
                # H1: Loop until you hit the required number of 'True'
                values_passed = 0
                j = 0
                while True:
                    value_picked: bool = optimistic_viable_vector_idx[j]
                    if value_picked:
                        values_passed += 1
                        if values_passed-1 == returned_id:
                            next_picked_vector_idx[i] = j
                            break
                    j += 1

                # picked_vector index
                if returned_id >= picked_id:
                    next_picked_vector_idx[i] += 1

            best_score = score

            # Convert from sorted matrix to input matrix IDs before returning
            matrix_id = sort_order[picked_id]
            next_picked_vector_idx = [sort_order[x] for x in next_picked_vector_idx]
            best_picked_vector_idx = [matrix_id] + next_picked_vector_idx

        return best_score, best_picked_vector_idx

字符串

也许这太天真了，但我想到的第一件事就是选择到目标距离最短的5列：

import scipy
import numpy as np
from sklearn.metrics.pairwise import pairwise_distances

def sparse_prod_axis0(A):
    """Sparse equivalent of np.prod(arr, axis=0)
    From https://stackoverflow.com/a/44321026/3381305
    """
    valid_mask = A.getnnz(axis=0) == A.shape[0]
    out = np.zeros(A.shape[1], dtype=A.dtype)
    out[valid_mask] = np.prod(A[:, valid_mask].A, axis=0)
    return np.matrix(out)

def get_strategy(M, target, n=5):
    """Guess n best vectors.
    """
    dists = np.squeeze(pairwise_distances(X=M, Y=target))
    idx = np.argsort(dists)[:n]
    return sparse_prod_axis0(M[idx])

# Example data.
M = scipy.sparse.rand(m=6000, n=1000, density=0.5, format='csr').astype('bool')
target = np.atleast_2d(np.random.choice([-1, 1], size=1000))

# Try it.
strategy = get_strategy(M, target, n=5)
result = strategy @ target.T

字符串
我突然想到，您可以添加另一个步骤，从M-target距离中提取前几个百分比，并检查它们的相互距离-但这可能非常昂贵。
我没有检查这与详尽的搜索相比如何。