帶偏好的貪心算法應用

吳平 方歡

摘要：文章針對傳統(tǒng)背包算法研究背包中物體權(quán)益值總和最大，存在無法根據(jù)用戶偏好選擇物品的缺陷，提出一種引入偏好值的方法，實現(xiàn)帶偏好的貪心算法應用。該方法擴大了背包問題的適用范圍。實驗結(jié)果表明所提出的方法具有較好的適用性。

關(guān)鍵詞：背包問題;貪心算法;滿意解;偏好值;擴展應用

中圖分類號：TP312 文獻標識碼：A

文章編號：1009-3044（2020）03-0096-02

1 背景

背包問題的求解無論是在理論上，還是在實踐中都具有重要意義。為了解決傳統(tǒng)背包問題無法根據(jù)用戶偏好選擇物品的缺陷，提出一種引入偏好值的方法。使得新的背包問題的解集更具有個性化。

2 問題的描述

2.1 傳統(tǒng)背包問題模型

傳統(tǒng)背包問題是眾所周知的一種經(jīng)典NP難組合優(yōu)化問題[1]，生活中許多問題都可以歸為此類。在傳統(tǒng)背包問題中[4]，輸入設(shè)定包含背包特定的容量，一系列具有重量和價值的物品。可行解為裝入背包的物體的選擇情況，其中選中物品的重量總和不能超過背包容量。求解的目標就是最大化選中物品的總價值。背包問題作為被廣泛求解的優(yōu)化問題，具有很強的普遍性。

2.2 帶偏好的貪心算法背包問題[2]

然而基于實際問題的需求以超市購物為例，購物者并不是要求背包中物體總價值最大，而是追求自己在可支配金額固定的情況，可以盡可能多的購買急需程度高的物體放人背包中。同樣，商場在某些時候追求銷量最大化，這時會稍微降低售價來吸引顧客。這樣的情況可歸納為保證利潤達到某個程度的前提下，實現(xiàn)銷量最大化。可能在某個時候[3]，當商場已經(jīng)擁有足夠的固定顧客時，商家改變策略，要求銷量保證在一定水平的前提下，實現(xiàn)利潤的最大化。這樣的實際問題有很多，總結(jié)起來可以發(fā)現(xiàn)，一般優(yōu)化問題不一定要求所有的目標值均獲得最大值。在特定的環(huán)境下，根據(jù)實際需求，背包問題中用來比較的權(quán)益值可以轉(zhuǎn)化為客戶對物體的需求程度，而其求解目標也可以轉(zhuǎn)化成滿足客戶需求的程度。

3 模型的建立

3.1 帶偏好的貪心算法描述

//AHP模型下的動態(tài)背包的貪心算法

Procedure AHP-GREEDY-KNAPSACK（Matrix，W，M，X，n）

//Matrix是用戶對準備裝入背包中的物體的做出的判斷矩陣，w（1：n）是

n件按將判斷矩陣進行層次分析法處理后得到權(quán)重按非遞增排序的價格。M是顧客可以支配的最大金額大小，X（1：n）是解向量//

real Matrix;

AHP（Matrix）//將判斷矩陣進行層次分析法處理//if CR<0.1//整個層次分析法通過了一直性檢驗//

Double demand

demand（l：n）←-AHP（Matrix）//層次分析法處理后的權(quán)重排序//endif exit

real W（l：n），X（l：n），M，cu;X←O//將解向量初始化為空//

cu ←M//cu是顧客可以支配金額的剩余容量//for i←l to ndo

if W（i》cu then exit endif X（i）←I

cu←cu-W（i） repeat

if i≤n then X（i） ←cu/W（i） endif end AHP-CREEDY-KNAP-SACK

3.2 帶偏好的背包算法數(shù)學模型

帶偏好的背包算法數(shù)學模型如下表示：

N

.

max”vi xi（l）

s.t.

Wwixi（2）

其中，xi =0或1，0≤i≤N;

公式（1）f2）為帶偏好的貪心算法背包問題模型的描述，目標函數(shù)即求解被選人背包中物品能最大限度地滿足客戶的需求，約束條件為被選中的物品的總價格不可以超過顧客可以支配的最大金額。在對每個物體的被急需程度的判斷上，層次分析法具有根據(jù)問題的性質(zhì)和要達到的總目標，將問題分解為不同的組成因素，并按照因素間的相互關(guān)聯(lián)影響以及隸屬關(guān)系將因素按不同層次聚集組合，形成一個多層次的分析結(jié)構(gòu)模型，從而最終使問題歸結(jié)為最低層（供決策的方案、措施等）相對于最高層（總目標）的相對重要權(quán)值的確定或相對優(yōu)劣次序的排定的特性。所以選擇使用層次分析法對每個物體在特定情況下被急需的程度進行權(quán)重分析并排序。

4 計算實例

4.1 運行過程示意圖

假設(shè)一位顧客帶了50元去超市購買東西，超市有五樣東西分別為面巾紙、零食、礦泉水、游戲機、水果。它們的價格和權(quán)益值固定，現(xiàn)對該顧客的三種狀態(tài)（餓不餓、渴不渴、是否很無聊）進行詢問，并判斷他購買哪幾種物品的可能眭較大。

假設(shè)該顧客很渴很餓但是不無聊，用原始的貪心算法和帶偏好的貪心算法求解結(jié)果如下（見圖1）：

假設(shè)該顧客有點渴不餓但是很無聊，用原始的貪心算法和帶偏好的貪心算法求解結(jié)果如下（見圖2）：

4.2 運行結(jié)果分析

由表l可看出，雖然帶偏好的貪心算法拿到物品的價值不如原始的貪心算法拿到的物品總價值多，但是帶偏好的貪心算法卻能更好地滿足客戶的實時需求，如圖1中，該顧客很渴很餓但是不無聊，在兩種貪心解中帶偏好的貪心算法把價值比較高的游戲機給舍棄而選擇比較解渴的礦泉水;在圖2中，該客戶的狀態(tài)是比較渴而且非常無聊，所以帶偏好的貪心解選擇了游戲機，在解渴方面的選擇時，帶偏好的貪心算法排除了價值更高的水果選擇了價值較低但是更容易解渴的礦泉水。

綜上所述，帶偏好的貪心算法雖然在物品總價值上不如原始的貪心算法，但在滿足客戶實時需求上，帶偏好的貪心算法要優(yōu)于原始的貪心算法。

5 結(jié)束語

文章主要介紹了帶偏好的貪心算法背包問題應用，該應用原理簡單，算法思路清晰，易于實現(xiàn)。

在帶偏好的貪心算法背包問題中，將權(quán)益值替換為物體被需求的權(quán)重大小進行貪婪求解，目標函數(shù)也相應地轉(zhuǎn)變?yōu)檫m合客戶需求的程度。會讓傳統(tǒng)的背包問題在數(shù)據(jù)挖掘、無人超市等領(lǐng)域具有很好的應用，擴展了傳統(tǒng)背包問題的適用范圍和功能。

參考文獻：

[1]王文東，武海妮，求解0-1背包問題的算法分析[J].信息與電腦：理論版，2018（9）：68-70.

[2]周嘯，李少梅，李森，等，一種基于局部貪心搜索的興趣旅游路線規(guī)劃算法[J].河北師范大學學報：自然科學版，2019，43（3）：262-268.

[3]周晨，基于網(wǎng)上訂單的智能超市研究設(shè)計[J].智庫時代，2019（22）：234-235.

[4]李霄鵬.貪婪算法與遺傳算法結(jié)合的建設(shè)項目合同優(yōu)化選擇[J]統(tǒng)計與決策，2019（6）：76-79.

[5]張芳.超市經(jīng)營的小數(shù)據(jù)挖掘思路研究[J]時代經(jīng)貿(mào)，2019（26）：58-59。