我正在尝试为我的问题找到一个名称，这样我就不必在编写解决问题的算法时重新发明轮子...
我已经说了 2,000 个二进制(行)向量，我需要从中选择 500 个。在选择的样本中，我进行列总和，我希望我的样本尽可能接近列总和的预定义分布。我将使用 20 到 60 列。
一个小例子:
向量之外:
110
010
011
110
100
我需要选择 2 以获得列总和 2, 1, 0。解决方案(在这种情况下是正确的)是
110
100
到目前为止我的想法
- 也许可以将其称为二进制多维背包，但我没有找到任何算法
- 线性规划可以提供帮助，但我需要一些逐步的解释，因为我没有这方面的经验
- 由于精确解并不总是可行的，模拟退火蛮力之类的方法可以很好地工作
- 想到了一种使用约束求解器的怪异方法 - 首先严格设置约束并逐渐放松它们，直到找到某种解决方案 - 考虑到 CSP 应该比 ILP 快得多...？<
最佳答案
我的具体、实用(如果近似保证对你有效)建议是应用最大熵方法(在 Boyd 和 Vandenberghe 的书 Convex Optimization 的第 7 章中；你可能会找到几个使用您最喜欢的搜索引擎实现)以找到行索引上的最大熵概率分布，使得 (1) 没有行索引更有可能超过 1/500 (2) 所选行向量的预期值是预定义的 1/500分配。给定此分布，独立选择每一行的概率是其分布可能性的 500 倍，这将平均为您提供 500 行。如果您需要恰好 500，请重复直到恰好达到 500(由于浓度限制，不应尝试太多次)。
关于algorithm - 二元向量的条件采样(？)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/57477865/