贪心算法在教辅教材经营管理系统中的应用

张光桃，蒋 然，梁 梁

（扬州职业大学，江苏 扬州 225009）

贪心算法在教辅教材经营管理系统中的应用

张光桃，蒋 然，梁 梁

（扬州职业大学，江苏 扬州 225009）

文章介绍了教辅教材经营管理系统的设计与实现方法，以及贪心算法在处理具体业务过程中的合理使用。在确定各类教辅书存放位置时，综合考虑了各类教辅书的盈利能力、库存量和热销程度，建立数学模型，使用贪心算法的设计思路得到问题的最优解，进而为各类教辅书在仓库的存放位置提供科学依据。

贪心算法；存放位置；管理；系统

随着大数据时代的到来，复杂数据成为很多应用系统开发者需要关注的问题，而且相关软件的业务复杂程度也在提升，应用系统数据量大并且相对复杂成为现实问题。在处理复杂数据时，为了提升数据处理速度，增强用户体现，就必须考虑处理问题的科学性和合理性，应用系统开发者或者开发团队除了要设计出合理的关系型数据库外，在表示端处理数据时还要考虑经典算法的使用，合理地使用经典算法可以既简便又高效地解决复杂问题[1]。

本文在实现教辅教材销售经营系统的过程中充分考虑业务处理的科学性，综合考虑各类教辅书的盈利能力、库存量和热销程度，建立数学模型，使用贪心算法确定各类教辅书在仓库的存放位置时，安排利润能力相对强的、库存量大的、热销的教辅书存放在离仓库出口更近的地方，保证补货更方便且减少了工作人员的搬运距离，提高工作人员的效率和仓库的使用率。

1 教材销售经营系统的设计与实现

1.1 系统需求分析

教辅教材销售经营系统软件根据客户提出的具体需要定制设计而成，系统主要完成订单销售与生产全过程，以及订单退货的流程管理。操作过程中涉及功能权限管理、财务管理和库存管理。不同用户类型对应不同的操作权限。订单和退货的完成过程如图1和图2所示。

图1 订单完成过程

图2 退货完成过程

系统需要完成以下主要功能：（1）订单导入与订单添加；（2）各级的订单审批；（3）信息统计；（4）产品价格管理；（5）财务管理；（6）库存管理；（7）用户与权限管理；（8）基本信息管理。

1.2 系统设计

为了便于团队开发和程序的扩展性能，选择使用三层架构+MVC设计模式来开发系统。整个应用系统在架构上分为三层（表示层、业务逻辑层、数据访问层）[2]，三层架构有利于解决整个应用程序各个业务操作过程中不同阶段的代码封装问题，有利于程序员更加专注地处理某阶段的业务逻辑[3]。

在三层架构中，表示层负责处理页面的显示与用户操作；数据访问层则封装了所有有关数据库的操作，提供方法返回用户需要的相应数据；而业务逻辑层则调用数据访问层的方法获取数据，再根据业务需要进行一些必要的业务处理，提供给表示层调用。三层架构遵从了“高内聚，低耦合”的框架设计思想[4]。

1.3 系统开发

依托河北衡水辉煌教育文化发展有限公司的业务支持和扬州国脉通信发展有限责任公司的技术支持，系统采用Microsoft Visual Studio 2010作为开发平台，使用C#作为基础语言，SQL Serv-er2008 R2作为后台数据库，进行了系统的开发。本系统涉及到MVC模式开发技术、三层架构设计技术、数据库操作、代码自动生成工具、自定义控件开发、LINQ技术、动态菜单技术、存储过程、面向对象等技术。本系统主页面如图3所示。

图3 教辅教材销售经营系统的主页面

2 贪心算法的基本知识

2.1 贪心算法概述

贪心算法是指对于某个问题，在处理过程中的每一步都做出当前最优的一步，即不从整体上考虑最优操作，只考虑当前某一时刻的最优解。贪心算法并非对任何问题都能得到整体的最优解，只有当每一步贪心选择都具有无后效性，即每一步选择的结果不会影响将来选择的各个变量。满足了无后效性，贪心算法每一步都选择当前时刻的最优解，由每一步的局部最优解构成整个问题的最优解，否则贪心算法只能是某一个问题的近似算法，无法得到最优解。如果解决问题每一步的局部最优解可以得到整个问题的最优解，可以选择使用贪心算法[5]。

2.2 贪心算法解题步骤

使用贪心算法解题可以分为以下4步：（1）将实际问题建立数学模型；（2）将整个问题分解为若干子问题；（3）针对每一子问题，求解得到该问题的最优解；（4）将子问题局部最优解进行合并，还原为原问题的一个解。

3 贪心算法在安排教辅书存放位置过程中的应用

在教辅教材经营管理系统的库存管理模块中，需要科学合理地安排各类教辅书在仓库的存储位置。在确定教辅书储存位置时，应根据教辅书的类别、利润能力、库存量和热销程度，并结合仓库保管场所的建筑结构特点、容量、装卸设备等条件，将仓储库房分为若干储存区域，从而对货物进行分区分类存放，尽量方便库存量大的、热销的、利润能力强的教辅书出库和入库，减少工作人员的搬运距离，提高工作效率，从而使得仓储管理更加科学合理。

3.1 建立数学模型

问题：假设系统中有N类教辅书，每种教辅书库存量为SN（N取值0~N-1，为教辅书对应的编号），利润为PN，每本书库存量KN，热销程度HN= KNmax，仓库中有M个库存位，到仓库的出口距离为WM，求每个存放点SP存放的教辅书编号SPN。

3.2 采用贪心算法获得局部最优解

为了让销量更好，即存取更频繁的库存位更靠近仓库出口，我们对每个库存位进行贪心搜索。对于搜索过程中某一时间对应的库存位，选择存放当前剩余教辅书中热销程度最高的一箱。

3.3 证明贪心算法正确性

无后效性：每次热销程度最高的教辅书选择距离仓库出口最近的仓库位只与这一时刻的状态有关，这个选择的结果不会影响将来选择的各个变量。如果事先对每个仓库位距离仓库出口的距离进行排序，则每一时刻进行选择的教辅书都对应着当前时刻距离仓库出口最近的地方，因此，此时选择热销程度最高的教辅书就可以得到最优解，对于此问题，使用贪心算法可以得到最优解。

3.4 求解过程

使用贪心算法安排教辅书存放位置过程步骤如下：

Step1：计算各类教辅书的利润PN，各类教辅书最低库存量KNmin，以及各类教辅书最高库存量KNmax，将教辅书根据各自利润降序排序，得到序列SN(N取值0~N-1)，获取各类教辅书的库存量KN，定义一个最大利润指针P=N-1。

Step2：将每个仓库位距离仓库出口的距离DN大小降序排序。得到序列DSN(N取值0~N-1)。

Step3：判断此时是否存在未分配的仓库位，如果不存在，分配完毕。

Step4：判断此时的KP是否大于零，如果小于等于零，则将SP从序列中删除，即P=P-1。

Step5：将此时正在分配的仓库位的仓库号DSP对应存放教辅书SP。

Step6：重复Step3～5。

4 结语

教辅教材经营管理系统是相关企业的定制管理系统，实现了订货、生产、退货、财务管理、仓库管理、用户管理、信息统计等管理功能，实现了企业的信息化管理。在确定教辅书在仓库中的存放位置时，综合考虑各类教辅书的利润能力、库存量和热销程度因素，使用了贪心算法进行迭代求解，科学合理地为各类教辅书确定了最优的存放位置。

[1]姚菊菊.贪心算法的探讨及其在船舶领域的应用[J].造船技术,2015(6):22-25,37．

[2]李玉荣.基于.NET的三层架构模式分析及应用[J].电脑编程技巧与维护,2015(8):83．

[3]任广震,侯进,王献.MVC模式在B/S结构政务系统的应用研究[J].计算机应用与软件，2014(8):54-58,74.

[4]赵伟,王志华,周兵.基于.NET技术和MVC的新架构模式[J].计算机工程与设计,2012,33(7):2646-2651．

[5]Thomas H.Cormen,Charles E.Leiserson,Ronald L. Rivest,等.算法导论:第3版[M].殷建平,徐云,译.北京:机械工业出版社,2012．

（责任编辑 杨荔晴）

The Discussion of Greedy Algorithm and Its Application In The Teaching Materials Sales Management System

ZHANG Guang-tao,JIANG Ran,LIANG Liang
（Yangzhou Polytechnic University,Yangzhou Jiangsu 225009,China)

ract:This paper introduces the design and implementation of teaching materials sales management system and the reasonable use of the greedy algorithm in the process of dealing with the specific business process.To de-termine the types of books stored position,considering the all kinds of books of profitability,inventory and sales level,establish mathematical model,using the greedy algorithm design ideas get the optimal solution,and then provide a scientific basis for all kinds of books in the warehouse storage location.

rds:greedy algorithm;storage location;management;system

TP301.6

A

1671-0142（2016）05-0035-03

张光桃(1980-)，男，安徽天长人，讲师，硕士,研究方向为计算机软件技术与应用.

江苏省教育科学“十二五”规划课题（D/2013/03/129，课题负责人：缪勇，张光桃）.