使用最小费用最大流模型解决酒店管理收益最大化问题

Posted on

最近老师布置个作业,很没有头绪,于是各种咨询,大家的解决方案是使用最小费用最大流模型来求解,于是我便花了3天时间来理解这个算法.

问题描述

问题很简单,你有一个只有5个房间的酒店,然后本周会有18个订单到来,怎样接受订单可以使本周的收益达到最大值.也就是把这18个订单填写到一个 5*7的表格里 怎么填收益最大,订单要么接受要么拒绝,也可以说是典型的01背包问题吧,但用动态规划不好抽象出来状态转移方程,所以我还是选择用最大流来做.每个订单包含3个信息:每晚付的房费,从周几开始入住,入住几天.

抽象数据模型

因为题目要求是球最大收益,而流模型是最小费用,所以我们把收益取相反数即可.关键是建立容量和权值,因为房间的数量是5,所以限制源点和汇点的容量是5,权值是0.然后中间设置8个点,产生7条边,每条边代表每天的流,权值为0,容量为无穷大.这里我们不能简单的连接点来设置订单的边,因为有相同的起始日期和结束日期的订单.这样会造成冲突,如何解决冲突呢? 我们可以在订单的边上再加一个顶点来进行区分.模型图如下所示: model 顶点11和顶点16是重复边的订单,对应的是第一个订单和第6个订单.源码和输入数据可以在文章末尾看到.

查找增广路径

这里我们使用Ford–Fulkerson算法来计算每次的增广路径.

路径的查找

每次增广路径的查找都需要得到最小权值的路径.查找路径使用的是SPFA算法.

第一次查找增广路径

model

第一次查找增广路径

model

以此类推求出最后的结果~

参考:

Source code

Ford–Fulkerson

tagged: algorithm
comments powered by Disqus