二元向量的条件采样（？）

Question

我正试图为我的问题找到一个名字，所以在编写解决问题的算法时不必重新发明轮子。

我说有2,000个二进制（行）向量，我需要从中选择500个。在选取的样本中，我进行列求和，并且我希望我的样本尽可能接近列和的预定义分布。我将处理20至60列。

一个小例子：

在向量之外：

110
010
011
110
100

我需要选择2来获取列总和2, 1, 0。解决方案（在这种情况下准确）是

110
100

到目前为止我的想法

• 也许可以把它称为二进制多维背包，但是我没有找到任何算法
• 线性编程可能会有所帮助，但由于我没有经验，因此需要逐步说明
• 因为精确的解决方案并不总是可行的，所以模拟退火蛮力之类的方法可能会很好地工作
• 考虑到CSP应该比ILP快得多……，想到一种使用约束求解器的怪异方法-首先将约束设置得很紧，然后逐渐松开它们，直到找到某种解决方案为止。

Answer 1

首先我对这个问题做一些假设：

• 无论所选解决方案的列总和高于还是低于目标，其权重都是相同的。
• 第一、第二和第三列的总和在解决方案中的权重相等（即，如果有一个解决方案，而第一列总和相差 1，而另一个解决方案的第三列总和相差 1，则该解决方案同样好）。

我能想到的最接近的问题是子集和问题，它本身可以被认为是背包问题的一个特例。

然而，这两个问题都是 NP 完全问题。这意味着没有多项式时间算法可以解决它们，尽管很容易验证解决方案。

如果我是你，这个问题的两个最有效的解决方案是linear programming和machine learning。

根据您在此问题中优化的列数，通过线性编程，您可以控制解决方案的微调程度，以换取时间。您应该阅读此内容，因为这相当简单且高效。

使用机器学习，您需要大量数据集（向量集和解决方案集）。您甚至不需要指定您想要什么，很多机器学习算法通常可以根据您的数据集推断出您希望它们优化的内容。

两种解决方案各有利弊，您应该根据情况和问题集自行决定使用哪一种。