多属性约束样本选择问题的求解工具问询（类多属性背包问题）

API 探路者

2026-4-22

问题描述

我手头有$N$个机器学习模型的训练样本，但只能从中选出数量远小于$N$的$n$个样本（即$n \ll N$）。这些样本都带有$K$个已测量的属性${a_1, a_2, \cdots, a_k}$。我想要选出这$n$个样本，同时满足两个核心目标：

让这$K$个属性列的总和尽可能大
各属性的权重分布尽可能均匀

我的尝试

我觉得这个问题有点像多属性版本的背包问题，但直接谷歌搜索下来，没找到太多能直接用来解决这个问题（或者它的松弛版本）的现成软件包，所以来社区问问大家有没有合适的工具推荐。

数值示例

给大家举个具体的小例子：我要从$N=5$个样本里选$n=3$个，样本有$K=4$个属性，原始数据如下：

序号	A	B	C	D
0	0.7	0.4	0.8	0.5
1	0.7	1.0	0.3	0.7
2	0.8	0.5	0.4	0.8
3	0.8	0.3	0.6	0.5
4	0.2	0.8	0.6	0.2

生成这份数据的代码如下：

import string
import itertools
import numpy as np
import pandas as pd

np.random.seed(42)
N = 5
n = 3
K = 4
measures = np.linspace(0.1, 1, 10)

df = pd.DataFrame(
    data=np.random.choice(measures, size=(N, K)),
    columns=list(string.ascii_uppercase)[:K],
)

我枚举了所有可能的选法，得到如下结果：

序号	选中样本索引	A	B	C	D
0	(0, 1, 2)	2.2	1.9	1.5	2
1	(0, 1, 3)	2.2	1.7	1.7	1.7
2	(0, 1, 4)	1.6	2.2	1.7	1.4
3	(0, 2, 3)	2.3	1.2	1.8	1.8
4	(0, 2, 4)	1.7	1.7	1.8	1.5
5	(0, 3, 4)	1.7	1.5	2	1.2
6	(1, 2, 3)	2.3	1.8	1.3	2
7	(1, 2, 4)	1.7	2.3	1.3	1.7
8	(1, 3, 4)	1.7	2.1	1.5	1.4
9	(2, 3, 4)	1.8	1.6	1.6	1.5