arrays - 算法 - 如何从数组中的每一列中选择一个数字，以便它们的总和尽可能接近特定值

Question

我有一个 m x n 实数矩阵。我想从每一列中选择一个值，以便我选择的值的总和尽可能接近预先指定的总数。

我不是一个经验丰富的程序员(尽管我有一个经验丰富的 friend 会提供帮助)。我想使用 Matlab、Mathematica 或 c++(必要时使用 MySQL)来实现这一点。代码只需要运行几次，每隔几天运行一次——不一定需要优化。我将有 16 列和大约 12 行。

Answer 1

通常我会建议使用动态规划，但这种情况的一些特征建议采用替代方法。一是性能要求轻；这个程序只会运行几次，听起来好像运行几个小时不会有问题。其次，矩阵相当小。第三，矩阵包含实数，因此有必要四舍五入，然后进行稍微复杂的搜索，以确保不会错过最佳可能性。

相反，我将建议使用以下半蛮力方法。 12**16 ~ 1.8e17 ，可能的选择总数太多了，但是 12**9 ~ 5.2e9用蛮力是可行的，并且12**7 ~ 3.6e7适合内存。计算前七列的所有可能选择。按总数对这些可能性进行排序。对于最后九列的每个可能选择，使用有效的搜索算法在前七列中找到最佳伴侣。 (如果你的内存很大，你可以试试八和八。)

我会尝试使用 C++ 中的第一个实现，使用 std::sort和 std::lower_bound来自 <algorithm>标准标题。测量它；如果它太慢，那么试试内存中的 B+-树(Boost 有吗？)。

---

我花了更多时间思考如何以最简单的方式实现我上面写的内容。这是一种适用于内存大约为 4 GB 的 64 位机器上的 12 x 16 矩阵的方法。

前八列的选择数是12**8 .每个选择都由 0 之间的 4 字节整数表示。和 12**8 - 1 .解码选择索引 i ，第一列的行由 i % 12 给出.更新i /= 12; .第二列的行现在由 i % 12 给出等等。

包含所有选择的向量大约需要 12**8 * 4字节，或大约 1.6 GB。两个这样的向量需要 3.2 GB。为前八列准备一个，为后八列准备一个。按它们指示的条目总和对它们进行排序。使用鞍背搜索找到最佳组合。 (将迭代器初始化为第一个向量，将反向迭代器初始化为第二个向量。虽然两个迭代器都不在其末尾，但将当前组合与当前最佳组合进行比较，并在必要时更新当前最佳组合。如果当前组合总和为目标，增加第一个迭代器。如果总和大于目标，增加第二个迭代器。)

我估计这需要不到 50 行 C++。