面对2000笔金额记录的凑数最优问题，你学了python竟然束手无策？
面对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 函数。
现在看看目前为止做了什么事情。
- 定义了一组变量
- 定义了目标函数
- 定义了一个约束条件，每个 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 还可以解决排班问题、路径最优、解答数独游戏等等。以后有机会再分享。