带偏好的贪心算法应用

吴平 方欢

摘要：文章针对传统背包算法研究背包中物体权益值总和最大，存在无法根据用户偏好选择物品的缺陷，提出一种引入偏好值的方法，实现带偏好的贪心算法应用。该方法扩大了背包问题的适用范围。实验结果表明所提出的方法具有较好的适用性。

关键词：背包问题;贪心算法;满意解;偏好值;扩展应用

中图分类号：TP312 文献标识码：A

文章编号：1009-3044（2020）03-0096-02

1 背景

背包问题的求解无论是在理论上，还是在实践中都具有重要意义。为了解决传统背包问题无法根据用户偏好选择物品的缺陷，提出一种引入偏好值的方法。使得新的背包问题的解集更具有个性化。

2 问题的描述

2.1 传统背包问题模型

传统背包问题是众所周知的一种经典NP难组合优化问题[1]，生活中许多问题都可以归为此类。在传统背包问题中[4]，输入设定包含背包特定的容量，一系列具有重量和价值的物品。可行解为装入背包的物体的选择情况，其中选中物品的重量总和不能超过背包容量。求解的目标就是最大化选中物品的总价值。背包问题作为被广泛求解的优化问题，具有很强的普遍性。

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。