面对2000笔金额记录的凑数最优问题，你学了python竟然束手无策？

好不容易学了一门编程语言 Python，又懂一点 Excel 操作，感觉自己无所不能了。直到有一天遇到了凑数最优问题，看似很简单，但始终无法解决。

凑数问题：在很多数值数据当中，不限制个数（或一些限制条件），选择出一些数据，这些数据的数值之和要等于一个或最接近与定值。比如：在 [2,1,17,34,3,8,47,9,30]中挑出几个和等于或最接近于100的数值

熟悉 Excel 的小伙伴一定知道规划求解功能，于是你怀着期待的心情打开它，结果只是出来这样子的提示

原来，超过200笔数据是需要用它的收费版本。

相信我，就算只有100多笔数据，它的求解速度也会难以满足你。我可不希望 Excel 卡你半天的时间。

今天，我就来教大家如何使用 python 的 or tools 解决凑数最优问题。

需要安装这些库：

这里有视频版本： http://mpvideo.qpic.cn/0bc3haaa6aaaiaagudfb2zrvaogdb44aadya.f10002.mp4?dis_k=22028126e2e35719673191845db90ca1&dis_t=1675941463&play_scene=10400&vid=wxv_2716724281359220739&format_id=10002&support_redirect=0&mmversion=false

理解流程

库的使用，只不过是一些函数的堆砌。关键在于理解大概的优化流程，否则你是不可能使用 or tools 得到你要的效果。

下面我用少量数据讲解，以便你更好理解。

• 可以看到，简单的7笔数据。目标值是9。

首先我们需要定义一列变量 x ，这里的 x 表示是否取出该笔金额。0 表示不取，1 表示取出

• 为什么说是变量呢？因为稍后程序会不断改变它们的值。

接着，定义目标函数。目标函数需要变量参与其中。在这个问题里面，我们需要用每一笔的金额 乘以变量 x，然后求和。

• 这里使用 SUM PRODUCT 函数。

现在看看目前为止做了什么事情。

1. 定义了一组变量
2. 定义了目标函数
3. 定义了一个约束条件，每个 x 只能取0或1

我们的目标是，通过修改变量 x 的值，使得目标函数最大化。但这些定义就足够了吗？我们来测试一下。

• 首先，第一个 x 取1 。
• 目标函数结果满足了所有约束条件，但不是最大化。
• 于是，第二个 x 取1。以此类推，直到第四个 x 取1。发现目标函数超过了9

此时，从第一个 x 为1开始的搜索找不到结果，退回一开始的全是0的状态。现在换第二个 x 取1开始，直到第四个x取1，得到结果

上面的过程只是一种简单表述，实际程序会做很多优化步骤。

现在可以总结一下关键流程：一，定义变量，设定变量取值的约束 二，定义目标函数 三，设定目标函数的约束 四，使目标函数最大化

接下来，带着这四点步骤，就可以轻松使用 or tools。

用 or tools 表达问题

首先，导入相关的库

使用 pandas 加载数据

设置好指定金额值

接下来，就是使用 or tools 。

• 行1：实例化 model ，我们将使用它进行变量创建，定义约束等一系列操作。
• 行4：使用 model 创建一列变量。注意，在创建变量的时候，分别指定了最小值、最大值、以及变量的名字。
• 行5：为了方便计算，添加到表格中
• 行10：定义目标函数。按照之前的讲解，每一条记录的金额与 x 相乘，然后求和。
• 行13：设定目标函数的约束。也就是小于等于指定值
• 行16：最大化目标函数

一切就绪，使用求解器求解。

• 行1：创建一个求解器
• 行3：调用求解器的函数，传入之前构造的 model
• 行5：其返回值可以表示是否找到最优解

可以看到目标函数结果与指定值一致。

但我们需要知道，目标函数的结果是来自于哪些记录。也就是每一个变量 x 的取值。

只需要把每个变量 x，给求解器转换，就可以得到变量值。这里我们在表格中新增一列，查看结果

到这里，肯定有人会认为，"自己用 Python 的 itertools 中的排列组合也能做到"

注意看左下角的运行时间，这个库是在 C++ 中执行运算。而且它使用的是最先进的算法。作为学习可以自己实现，但在产生工作切忌心高气燥

添加更多约束条件

在实际工作需求中，往往会存在更多的限制条件。比如本来超过指定成本值等等。

接下来看看需求进阶。

看看结果中，每个组别抽取了多少笔记录。

可以看到，总共26个组别，其中一些组别被抽取了多于10笔的记录

现在可以考虑第二个需求。我们希望在每个组别抽取的数量不能多于10笔，这种情况还能找到凑数结果吗？

回到之前定义约束的代码。

• 行13-15：对表格数据按组别分组，每一组数据中，对该组别中的所有变量 x 的总和，限定在10以内。
• 注意， 所有的约束条件都记录放入 model 中

重新执行得到：

可以看到仍然找到最优解。

再次获取变量的值，然后看看每个组别的抽取数量。

完全符合要求

不要忘记一键三连。你的点赞、收藏、关注，是我创作的动力。

今天就分享到这里。从本期例子中可以看到，凑数问题在找到最优解的情况下，是有可能出现多个组合答案。那么，怎么可以列出所有符合要求的组合答案呢？

此外，or tools 还可以解决排班问题、路径最优、解答数独游戏等等。以后有机会再分享。