寻找元素与最大总参数值的最佳组合

Question

我有100个元素。每个元素有4个特征A，B，C，D。每个特征是一个整数。

我想为每个特性选择2个元素，这样我一共选择了8个不同的元素。我要最大化这8个特征A，A，B，B，C，C，D，D的和。

贪婪的算法是选择A最高的两个元素，然后在其余元素中选择B最高的两个元素，但是这可能不是最优的，因为具有最高A的元素也有更高的B。

我们有算法来最优地解决这个问题吗？

Answer 1

这可以作为一个最小成本流问题来解决。特别是，这是一个赋值问题

首先，我们只需要每个特性中的8个最好的元素，这意味着最多需要32个元素。甚至应该可以进一步减少搜索空间(如果A的2个最佳元素不是任何其他特性中最好的6个元素之一，我们已经可以将这2个元素分配给A，而彼此的特性只需要查看前6个最佳元素。如果不清楚原因，我会进一步解释)。

然后构造顶点S，T和Fa，Fb，Fc，Fd和E1，E2，...E32，具有以下边：

• 对于每个顶点Fx，一个从S到Fx的边，最大流2，权重为0(正如我们希望每个特性有2个元素)。
• 对于每个顶点Ei，如果Ei是特征x的最高元素之一，则从Fx到Ei的边缘，其最大流量1和权重等于特征x的负值。(否定，因为算法会找到最小的成本)
• 对于每个顶点Ei，一个从Ei到T的边，最大流量为1，重量为0。(因为每个元素只能选择一次)

我不确定这是不是最好的方法，但它应该有效。

Answer 2

正如per @AloisChristen所建议的，这可以写成一个赋值问题：

• 一方面，我们为每个特性选择了8个最佳元素，即32个或更少的元素，因为一个元素可能是多个特性的最佳元素；
• 在另一边，我们放了8个座位A，A，B，B，C，C，D，D
• 解决由此产生的分配问题。

这里使用优化函数解决了这个问题

from numpy.random import randint
from numpy import argpartition, unique, concatenate
from scipy.optimize import linear_sum_assignment

# PARAMETERS

n_elements = 100
n_features = 4
n_per_feature = 2

# RANDOM DATA

data = randint(0, 21, (n_elements, n_features))  # random data with integer features between 0 and 20 included

# SELECT BEST 8 CANDIDATES FOR EACH FEATURE

n_selected = n_features * n_per_feature
n_candidates = n_selected * n_features
idx = argpartition(data, range(-n_candidates, 0), axis=0)
idx = unique(idx[-n_selected:].ravel())
candidates = data[idx]
n_candidates = candidates.shape[0]

# SOLVE ASSIGNMENT PROBLEM

cost_matrix = -concatenate((candidates,candidates), axis=1)  # 8 columns in order ABCDABCD
element_idx, seat_idx = linear_sum_assignment(cost_matrix)
score = -cost_matrix[element_idx, seat_idx].sum()

# DISPLAY RESULTS

print('SUM OF SELECTED FEATURES: {}'.format(score))
for e,s in zip(element_idx, seat_idx):
    print('{:2d}'.format(idx[e]),
          'ABCDABCD'[s],
          -cost_matrix[e,s],
          data[idx[e]])

输出：

SUM OF SELECTED FEATURES: 160
 3 B 20 [ 5 20 14 11]
 4 A 20 [20  9  3 12]
 6 C 20 [ 3  3 20  8]
10 A 20 [20 10  9  9]
13 C 20 [16 12 20 18]
23 D 20 [ 6 10  4 20]
24 B 20 [ 5 20  6  8]
27 D 20 [20 13 19 20]