image

前言

前段時(shí)間有個(gè)朋友去參加一個(gè)知名外企的人工智能崗位，其中有一道上機(jī)測試題目，具體題目翻譯成中文如下：

中國電信推出多個(gè)電信套餐, 每個(gè)套餐包含不同的服務(wù)，每個(gè)套餐有不同的價(jià)格。如下表所示:

image

如果用戶購買服務(wù)A,B,D最優(yōu)的組合是什么?

為了解這個(gè)題目，我們列出所有滿足A,B,D要求的可能性。

image

對于這個(gè)題目,我們很容易就可以目測出來應(yīng)該選擇plan1 + plan3 總費(fèi)用為225.

為了滿足A,B,D的服務(wù)，我們有其它的選擇可能性，比如plan1 + plan2 總費(fèi)用250。顯然，這個(gè)比225要貴，不能選。

解題思路

• 窮舉法

窮舉法思路很簡單，就是把不同的plan組合起來，得出每個(gè)組合可以提供什么服務(wù)，然后根據(jù)想要的服務(wù)，查表得出。

image

image

然而窮舉查表法有一個(gè)問題，當(dāng)增加一個(gè)plan之后，計(jì)算的復(fù)雜度成幾何級增長，如果有100個(gè)plan,計(jì)算量就相當(dāng)巨大了。

• 背包算法

[背包算法]這里不詳說，可以參考百度百科進(jìn)行解題。

• 線性規(guī)劃

  關(guān)于什么是[線性規(guī)劃]，可以參考一下百度百科.

  解線性規(guī)劃大概有以下幾個(gè)步驟：

  1. 定義目標(biāo)函數(shù)

  2. 定義約束條件

  3. 規(guī)劃求解

  在這個(gè)面試題目中，我們可以根據(jù)線性規(guī)劃的思路進(jìn)行求解。

• 解題步驟

  • 定義目標(biāo)函數(shù)

  設(shè)以下參數(shù)

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

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

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

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

  由于我們這道題目中，每一個(gè)未知數(shù)都必須是整數(shù)，即不存在采用0.5個(gè)plan1的說法。x0只能求解出來是0,或者1.

  所以，我們這里只能使用線性規(guī)劃中的整數(shù)規(guī)劃，即任何一個(gè)解均為整數(shù)，不能為小數(shù)。

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

其中100是指plan1的價(jià)格。150,125,135 分別是plan2,plan3,plan4的價(jià)格。

我們的目標(biāo)是，使這個(gè)函數(shù)在后續(xù)約束的條件下，達(dá)到最小值。

• 定義約束條件

在列出約束條件之前，我們把已知的條件先整理成表格，這個(gè)可以更容易理解后續(xù)定義的約束條件。

image

目前題目要求必須有A,B,D三項(xiàng)服務(wù)。

A服務(wù)

A列中可以看出要只有plan1,plan3為1，其它都為0，列出第一個(gè)約束條件x0 + x3 >= 1; 也即plan1與plan3必須要有其中一個(gè)，有能提供A服務(wù)。

B服務(wù)

B列中，只有plan1,plan2為1，其它為0;列出第二個(gè)約束條件x0 + x1 >=1; 也即plan1,plan2必須有其中的一個(gè)，才能提供B服務(wù)。

C服務(wù)

x1 + x3 >=1 原理與上面相同，不詳細(xì)說明。

D服務(wù)

x1 + x2 + x3 >= 1 原理與上面相同，不詳細(xì)說明。

• 解題

  有了目標(biāo)函數(shù)，有了約束條件，就可解題了。在解題時(shí)，我使用了pulp開源庫。

  具體代碼如下所示

from pulp import *

使用上述代碼，可以正確的解出

x0 = 1.0；

x1 = 0.0；

x2 = 1.0；

x3 = 0.0；

總費(fèi)用為 225.0

也即采用plan1 + plan3; 總費(fèi)用為225.0

似乎已經(jīng)解決問題了，然而，plan是可能增減的，價(jià)格是可能調(diào)整的；目標(biāo)選擇的套餐也是需要變化的，今天要求A,B,D;明天可能就要求AEF了。 這要求我們把上述代碼泛化一下，以適應(yīng)不同的要求。

• 泛化

我們希望建立一個(gè)lowest函數(shù)，只要把plan列表輸進(jìn)去，目標(biāo)選擇的套餐輸進(jìn)去，然后就返回相應(yīng)的結(jié)果，那就完美了。

就好像這樣

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

期待這個(gè)lowest函數(shù)能返回: 148.0 ['plan3', 'plan5']

直接貼代碼:

from pulp import *

上述代碼中，我限制了套餐個(gè)數(shù)只有10個(gè)，然而，這個(gè)可以根據(jù)實(shí)際要求，可以擴(kuò)展。

上述代碼中，其實(shí)還可以使用numpy 三維數(shù)組來描述plan數(shù)據(jù)，這樣可以簡化代碼，這個(gè)可以留給讀者進(jìn)行。