2020-07-28

image

前言

前段时间有个朋友去参加一个知名外企的人工智能岗位，其中有一道上机测试题目，具体题目翻译成中文如下：

中国电信推出多个电信套餐, 每个套餐包含不同的服务，每个套餐有不同的价格。如下表所示:

image

如果用户购买服务A,B,D最优的组合是什么?

为了解这个题目，我们列出所有满足A,B,D要求的可能性。

image

对于这个题目,我们很容易就可以目测出来应该选择plan1 + plan3 总费用为225.

为了满足A,B,D的服务，我们有其它的选择可能性，比如plan1 + plan2 总费用250。显然，这个比225要贵，不能选。

解题思路

• 穷举法

穷举法思路很简单，就是把不同的plan组合起来，得出每个组合可以提供什么服务，然后根据想要的服务，查表得出。

image image

然而穷举查表法有一个问题，当增加一个plan之后，计算的复杂度成几何级增长，如果有100个plan,计算量就相当巨大了。

• 背包算法

[背包算法]这里不详说，可以参考百度百科进行解题。

• 线性规划

  关于什么是[线性规划]，可以参考一下百度百科.

  解线性规划大概有以下几个步骤：

  1. 定义目标函数

  2. 定义约束条件

  3. 规划求解

  在这个面试题目中，我们可以根据线性规划的思路进行求解。

• 解题步骤

  • 定义目标函数

  设以下参数

  x0: 是否采用plan1. x0 >= 0; x0 <= 1

  x1: 是否采用plan2. x0 >= 0; x0 <= 1

  x2: 是否采用plan3. x0 >= 0; x0 <= 1

  x3: 是否采用plan4. x0 >= 0; x0 <= 1

  由于我们这道题目中，每一个未知数都必须是整数，即不存在采用0.5个plan1的说法。x0只能求解出来是0,或者1.

  所以，我们这里只能使用线性规划中的整数规划，即任何一个解均为整数，不能为小数。

Zmin = 100 * x0 + 150 * x1 + 125 * x2 + 135 * x3

其中100是指plan1的价格。150,125,135 分别是plan2,plan3,plan4的价格。

我们的目标是，使这个函数在后续约束的条件下，达到最小值。

• 定义约束条件

在列出约束条件之前，我们把已知的条件先整理成表格，这个可以更容易理解后续定义的约束条件。

image

目前题目要求必须有A,B,D三项服务。

A服务

A列中可以看出要只有plan1,plan3为1，其它都为0，列出第一个约束条件x0 + x3 >= 1; 也即plan1与plan3必须要有其中一个，有能提供A服务。

B服务

B列中，只有plan1,plan2为1，其它为0;列出第二个约束条件x0 + x1 >=1; 也即plan1,plan2必须有其中的一个，才能提供B服务。

C服务

x1 + x3 >=1 原理与上面相同，不详细说明。

D服务

x1 + x2 + x3 >= 1 原理与上面相同，不详细说明。

• 解题

  有了目标函数，有了约束条件，就可解题了。在解题时，我使用了pulp开源库。

  具体代码如下所示

from pulp import *

使用上述代码，可以正确的解出

x0 = 1.0；

x1 = 0.0；

x2 = 1.0；

x3 = 0.0；

总费用为 225.0

也即采用plan1 + plan3; 总费用为225.0

似乎已经解决问题了，然而，plan是可能增减的，价格是可能调整的；目标选择的套餐也是需要变化的，今天要求A,B,D;明天可能就要求AEF了。 这要求我们把上述代码泛化一下，以适应不同的要求。

• 泛化

我们希望建立一个lowest函数，只要把plan列表输进去，目标选择的套餐输进去，然后就返回相应的结果，那就完美了。

就好像这样

plans = {"plan1" : ("AB", 100),

期待这个lowest函数能返回: 148.0 ['plan3', 'plan5']

直接贴代码:

from pulp import *

上述代码中，我限制了套餐个数只有10个，然而，这个可以根据实际要求，可以扩展。

上述代码中，其实还可以使用numpy 三维数组来描述plan数据，这样可以简化代码，这个可以留给读者进行。