贪心法求解一般背包问题的教学探讨

余亮　柯昌博　赵学健

摘 要： 讨论了算法分析与设计课程中一般背包问题的贪心法求解策略，提出了单位重量价值作为最优量度标准的数学依据。该数学依据有助于加深学生对如何选取最优量度标准的理解并提高学生对贪心法的掌握程度。

关键词： 贪心法； 一般背包问题； 最优量度标准； 算法设计与分析

中图分类号：G642 文献标志码：B 文章编号：1006-8228（2016）01-71-02

Discussion on the teaching of solving general knapsack problem with greedy method

Yu Liang1， Ke Changbo2， Zhao Xuejian1

（1. College of Internet of Things， Nanjing University of Posts and Telecommunications， Nanjing， Jiangsu 210003， China；

2. College of Computer， Nanjing University of Posts and Telecommunications）

Abstract： Greedy method for solving the general knapsack problem in the course of algorithm analysis and design is discussed in this paper， and the mathematical basis of choosing unit weight value as the optimal metric is put forward. The mathematical basis is helpful to deepen students' understanding of how to select the optimal metric and improve the students' mastery of the greedy method.

Key words： greedy methods； general knapsack problem； optimal metric； algorithm design and analysis

0 引言

算法分析与设计作为高等教育中计算机及其相关专业的核心课程[1-2]，旨在培养学生使用计算机分析问题和解决问题的能力。在该课程中，最基本的算法设计方法包括分治法、贪心法、动态规划法等。贪心法最重要的两个关键词是：最优量度标准和最优子结构特性。所谓最优量度标准是指，可以根据该量度标准，对问题实现多步局部决策求解，虽然在该量度意义下所做的这些选择都是局部最优的，但最终得到的解是全局最优解；最优子结构特性表示问题的整体最优解包含了其子问题的最优解。在利用贪心法求解问题时，第一步要提出量度标准并证明该标准为最优量度标准，并证明问题具有最优子结构特性。相比最优子结构特性的证明而言，提出量度标准并证明该标准为最优量度标准更困难，其主要原因是量度标准的选择是仁者见仁、智者见智，种类可以有很多。在讲授贪心法求解一般背包问题时，通常给出3种量度标准：①每次取价值最大的物品装包；②每次取重量最小的物品装包；③每次将单位重量价值最大的物品装包。然后，通过实验来证明第3种量度标准在上述标准中是最优的。最后，证明选取的第3种量度标准为最优量度标准。这样的讲法虽然是循序渐进的，有助于学生逐步理解贪心法求解问题的主要步骤，但也有一个问题：当学生自己提出的量度标准中不包含标准3时，利用实验结果对比和证明来判定问题具有最优量度标准将不再凑效，这使学生对如何选取最优量度标准产生困惑。此时，若能告之学生单位重量价值作为最优量度标准的数学依据，让其明白最优量度标准的选取有章可循，并非随意想象或凭借经验得来，则有助于提高学生学习信心和教学效果。

基于以上观察，本文将首先给出一般背包问题的数学模型，然后提出单位重量价值作为贪心法中最优量度标准的数学依据，最后通过计算机仿真结果展示本文提出的数学依据与教材中贪心法采用的单位重量价值作为最优量度标准的一致性。

1 一般背包问题的数学模型

一般背包问题可描述如下：现有一个载重为M的背包和N个物品（物品可分割），其中第i（1?i?N）个物品的价值为pi，重量为wi，试给出一种装填方式，使得装入背包物品的总价值在不超过背包载重的前提下达到最大。

令xi表示第i个物品装入到背包中的部分，则有：0?xi?1。由于所有装入的物品不应超过背包的载重，故有：。最终，所装入物品总价值可表示为。根据一般背包问题的描述，可建立如下数学优化模型：

2 选取单位重量价值作为最优量度标准的数学依据

上一节建立的数学优化模型为凸优化问题[2]，其对应的拉格朗日函数如下：

根据KKT最优性条件[2]，所建模问题的最优解xi必须满足如下的条件：

其中：第1个为最小化条件；第2和第3个为原问题可行性条件；第4个为对偶问题可行性条件；第5-7个为互补松弛条件；ηi，εi，λ分别为约束xi?0，xi?1以及∑wixi-M的对偶变量。由于建模的问题是凸问题，满足上述条件的解同时也为最优解。下面分三种情况进行讨论：①当-pi+λwi>0时，有ηi>0，由条件5可知，必有xi=0。②当-pi+λwi<0时，有εi>0，由条件6可知，必有xi=1。③当-pi+λwi=0时，有ηi=εi=0，此时xi=0或xi=1或等于（M-∑wi'xi'）/wi，i'≠i）。换句话说，要得到最优的xi，需给出λ的最优值λ*，其值由约束∑wixi=M来确定。令λmin=minipi/wi，λmax=maxipi/wi。很明显，当λ从λmax逐渐减小时，∑wixi会单调递增至M，则此时的λ即为λ*。事实上，λ从λmax逐渐减小的过程，等价于贪心法每步决策时选取具有最大单位重量价值的物品的过程。因此，贪心法选取单位重量价值作为最优量度标准的数学依据在此体现。为了更加直观地展示该数学依据，我们进行了数值仿真并利用二分搜索快速找到λ*和最优装填决策。参数设置如下：M=14，N=4，[p1，p2，p3，p4]=[8，2，3，5]，[w1，w2，w3，w4]=[4，6，3，4]。最终得到的仿真结果如图1所示。

从图1可知，随着λ的降低，装填的物品逐渐增加，直至等于背包载重14。第1次迭代时，λ等于λmax=2和λmin=0.3333的中间值1.1667，此时，由于物品1和4的单位重量价值均大于1.1667，物品1和4均装入，故第1次迭代装入物品的总重量为8。当迭代结束时，最优决策是[1，0.5，1，1]，最大价值是17。上述整个物品装填过程及最终结果与贪心法中每次选取单位重量价值最大的物品装包所对应的装填过程和结果均一致。

3 结束语

贪心法求解问题的核心是选取最优量度标准。本文对贪心法求解一般背包问题时最优量度标准的选择进行了探讨，并给出了单位重量价值作为最优量度标准的数学依据。这有助于学生明白：虽然量度标准的选取可以有很多种，但最优的量度标准往往有其背后的数学依据可遵循，并非完全凭借经验或随意想象得来；同时有助于学生加深对选择最优量度标准的理解并提高学生掌握贪心法的信心。

参考文献（References）：

[1] 余祥宣，崔国华，邹海明.计算机算法基础[M].华中科技大学

出版社，2006.

[2] 陈慧南.数据结构与算法：C++语言描述[M].高等教育出版

社，2005.

[3] S. Boyd and L. Vandenberghe， Convex optimization[M].

Cambridge：Cambridge University Press，2004：1-244