我有50个列表，每个列表都有0和1。当你把50个列表放在一起时，我知道1的总比例。我想找出10个最接近1的列表。
我要最小化的函数是abs（mean（pooled subset）-mean（pooled full set））
对于那些了解熊猫的人：
就pandas而言，我有一个数据框架如下
等等，总共有50个标签，每个标签的值在100到1000之间。
我想找到10个标签的子集，其中d最小
d = abs(df.loc[df.label.isin(subset), 'Value'].mean() - df.Value.mean())
我试图将动态编程解决方案应用于背包问题，但问题是，每个列表（标签）对最终样本的贡献意味着取决于随后将包括哪些其他列表（因为它们将以不可预测的方式增加样本大小）。这就像背包问题，你挑选的每一个新物品都会改变你先前挑选物品的价值。很棘手。
有更好的算法来解决这个问题吗？
最佳答案
有一种方法，有点麻烦，将这个问题表示为MIP（混合整数规划）问题。
我们需要以下数据：
mu : mean of all data
mu(i) : mean of each subset i
n(i) : number of elements in each subset
N : number of subsets we need to select
我们需要一些二元决策变量
delta(i) = 1 if subset i is selected and 0 otherwise
优化问题的正式声明可以如下所示：
min | mu - sum(i, mu(i)*n(i)*delta(i)) / sum(i, n(i)*delta(i)) |
subject to
sum(i, delta(i)) = N
delta(i) in {0,1}
这里
sum(i, mu(i)*n(i)*delta(i))是所选项目的总值，sum(i, n(i)*delta(i))是所选项目的总数。目标显然是非线性的（我们有一个绝对值和一个除法）。这有时被称为MINLP问题（MINLP用于混合整数非线性规划）。虽然MINLP解算器是现成的，但我们实际上可以做得更好使用一些体操，我们可以将这个问题重新定义为一个线性问题（通过添加一些额外的变量和额外的不等式约束）。全部细节here。生成的MIP模型可以用任何MIP解算器求解。
有趣的是，我们不需要模型中的数据值，只需要对每个子集
n(i),mu(i)。