背包问题算法设计及分析

《背包问题算法设计及分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、万方数据于淼：“背包问题”算法设计及分析“背包问题”算法设计及分析于淼(辽宁鞍山气象局辽宁鞍山114004)摘要：“背包问题”是一个典型问题．其求解也是算法设计及验证的一个热点。在此分别采用优先策略、动态规划及递归三种不同方法对“背包问题”进行求解、算法设计及验证。实践证明了三种算法的正确性。在复杂度分析中，优先策略算法的空间及时间复杂度最低。而动态规划法具有明显的优势。关键词：背包算法；优先策略；动态规划；栈操作中图分类号：TP274文献标识码：B文章编号：1004—373X(2010)02一128一03DesignandAnalysisofKnapsackPr

2、oblemYUMiao(AnshanMeteorologicalBureauofLiaoningProvince，Anshan．114004，China)Abstract：Knapsackproblemistypicalproblemincomputerscienceanditssolutionisahotspotinalgorithmsdesignandverification．Thesolutionsfortheknapsackproblems，algorithmsdesignandverificationwiththreedifferentmeans：pre

3、ferencestrategy，dynamicprogrammingandrecursion．Correctnessofthesethreealgorithmsareproved，inthecomplexityanalysis，thecompiexityofspaceandtjmeinpreferencestrategyislowest，whilethedynamicprogramminghasobvioussuperiorjty．Keywords：knapsackproblem；preferencestrategy；dynamicprogramming；stac

4、kperation0引言算法研究是计算机科学的重要组成部分，有观点认为“计算机科学是一门研究算法的科学”[1’2]，无论这种观点是否全面，都足以说明算法研究在计算机科学发展中所具有的重要作用及地位。算法研究是通过程序来实践的。程序一算法+数据结构m”，这一大家都熟知的公式更加表明算法研究不是单纯的数学问题，必须通过“实践”掌握算法的实质。这里对“背包问题”采用优先策略、动态规划及递归三种不同方法进行求解、算法设计及验证。并通过各种算法予以实现。本文研究、分析了实现“背包问题”算法的实质。1问题描述一旅行者携带背包去登山，已知所能随身携带的背包重量限度为6，现有行种

5、物品可供选择装入背包。第i种物品重量为＆，，其重要性价值指标为∞旅行者应如何选择携带各种物品，以使总价值最大田^。“背包问题”的数学模型为：max2=∑啊。f=1约束条件为：收稿日期：2009一09—16128∑口m≤6，n。>o，f。>o，I=1z，一O或1，1≤i≤卵2优先策略的算法设计按重量al≥以2≥倪3≥口。≥⋯≥口，，对z，进行调整，作为待选队列。7’8I。假设前面已经选择了s个，即j¨j引⋯，歹。为最优选择的前s件物品，则应满足：％，fr。，⋯，f。，且∑口i<6对后面等待选择的物品j。来说，与之对应的口。无疑满足：·a女≤口i，!一1，2，⋯，s即

6、所选择的物品重量比其所有待选择的物品重量大。因此，对待选择的物品是否被选中将分为：∑盘。+f=1a。≤6和∑n。+以。>6两种情况。￡=1(1)对于∑日。+口。≤6的情况，将z。插入已选择的J队列中，然后根据c，的大小找到其相应的位置。(2)对于∑cz。+口。>6的情况，有：f萱l①若存在靠≥c。，则将z。插入并按f。排序后，将万方数据Ji从已选择的队列中删除并插入按c：从大到小、重量从小到大地排序到二次筛选队列中。②若存在c。k+c。>c。的物品z。插入已选择的J队列中并按r，排序，将从已选择的队列中删除并插入按c，从

7、大到小、重量从小到大排序到二次筛选队列中；若不存在满足的待选物品，则将z。插入到二次筛选队列中。③当待选队列为空时，选择队列从s到1与从二次筛选队列中选择的元素进行优化选择。若存在：∑口，+∑以。≤6，∑勺>f。将组合的各元素X，插入已选择的，队列中，然后根据c：的大小找到其相应的位置：j。，歹舯⋯，J。。④当③中已完成对首元素组合的筛选后，此时的，队列为最优选择。3动态规划法的算法设计动态规划的基础是最优化原理，其关键问题是建立动态规划的数学模型(状态转移方程)。主要步骤是：划分阶段，确定阶段的状态；确定决策变量、权函数以及指标函数；建立状态转移方程；根据动态规

8、划的最优化