文章标签 ‘图论’

超能饮料问题

今天讨论超能饮料的问题。这里是题目的来源。这个超能饮料的题目,颇有些炒作的嫌疑。据说这道题是程序员百万年薪招聘的题目之一。今天也是无意中从同学那里知道,这里就简单给出思路,然后给出Python语言的实现版本。

这里简单说一下超能饮料问题的大意。现在,已知有若干种原料,它们以C开头,比如:C1、C2.......一种原料转化为另一种原料需要使用定制的机器,而这也是成本主要来源(原料成本不计)。机器标记以M开头,如:M1、M2......

现在我们有一系列的输入(命令行参数形式,给出文件名,以文件形式读入),文件的每一行都代表特定的设备型号。每一行的格式如下:

<machine name>  <orig compound>  <new compound>  <price>(分别对应的中文意思是设备名称、源化合物、新化合物、价格)

输入文件示例:

M1  C1  C2  277317
M2  C2  C1  26247
M3  C1  C3  478726
M4  C3  C1  930382
M5  C2  C3  370287
M6  C3  C2  112344

题目的要求是,求无论能买到那种原料,都保证能生产出其他原料,并且保证花费的代价最小。

要求返回值的格式为:第一行,最优总价格。第二行,机器列表(去掉开头M),比如上例的输出示例:

617317
2 3 6

读完这条题目,我们可以发现,这题目其实是一条典型的图论题。对于某一个状态Ci,我们可以通过Mk转移至Cj,权重为Wm。于是,根据题意,我们实际上要求的是这样一条或者多条环路,使得它们包含所有的原料,并且,环路上所有的权重和最小。

在此基础上,我们必须满足两点。

  1. 这条环路必须包含所有的原料。如果不能满足包含全部原料,就不能保证“无论能买到哪种原料,都保证能生产出其他原料”的条件。
  2. 对于重复出现的状态转移,只需计算一遍。

综上所述,问题要解决的在已知图中求一条或多条环路,并且使这些环路中包含所有原料。

关于作者

残阳似血(@秦续业),程序猿一枚,把梦想揣进口袋的挨踢工作者。现加入阿里云,研究僧毕业于上海交通大学软件学院ADC实验室。熟悉分布式数据分析(DataFrame并行化框架)、基于图模型的分布式数据库和并行计算、Dpark/Spark以及Python web开发(Django、tornado)等。

博客分类

点击排行

标签云

扫描访问

主题

残阳似血的微博