帶偏好的貪心算法應用

吳平 方歡

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

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

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

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

1 背景

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

2 問題的描述

2.1 傳統背包問題模型

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

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

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

3 模型的建立

3.1 帶偏好的貪心算法描述

//AHP模型下的動態背包的貪心算法

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

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

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

real Matrix;

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

Double demand

demand（l：n）←-AHP（Matrix）//層次分析法處理后的權重排序//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 帶偏好的背包算法數學模型

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

N

.

max”vi xi（l）

s.t.

Wwixi（2）

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

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

4 計算實例

4.1 運行過程示意圖

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

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

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

4.2 運行結果分析

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

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

5 結束語

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

在帶偏好的貪心算法背包問題中，將權益值替換為物體被需求的權重大小進行貪婪求解，目標函數也相應地轉變為適合客戶需求的程度。會讓傳統的背包問題在數據挖掘、無人超市等領域具有很好的應用，擴展了傳統背包問題的適用范圍和功能。

參考文獻：

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

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

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

[4]李霄鵬.貪婪算法與遺傳算法結合的建設項目合同優化選擇[J]統計與決策，2019（6）：76-79.

[5]張芳.超市經營的小數據挖掘思路研究[J]時代經貿，2019（26）：58-59。