下载文档原格式
贪心算法是一种在解决问题的过程中追求局部最优的算法，对于一个有多种属性的事物来说，贪心算法会优先满足某种条件，追求局部最优的同时希望达到整体最优的效果。
以下是一些经典的贪心算法问题：1. 背包问题：给定一组物品，每个物品都有自己的重量和价值，背包的总容量有限。
贪心算法需要选择物品以最大化背包中物品的总价值，同时不超过背包的总容量。
这种问题可以有多种变体，例如分数背包问题和完全背包问题。
2. 硬币找零问题：给定一组硬币的面值和数量，以及需要找零的金额。
贪心算法需要选择硬币以最小化找零的总数量。
这个问题可以通过从大到小排序硬币，并从最大面值的硬币开始选择，直到找零的金额达到所需的总金额。
3. 区间选点问题：给定一系列闭区间，每个闭区间都有一个起始点和结束点。
贪心算法需要选择尽量少的点，使得每个闭区间内至少有一个点被选中。
这个问题可以通过对结束点进行排序，并从左到右选择结束点，直到下一个要选择的结束点与上一个选择的结束点之间的距离大于当前选择的结束点与上一个选择的结束点之间的距离为止。
4. 区间覆盖问题：给定一系列闭区间，贪心算法需要选择尽量少的区间，使得所有区间都被覆盖。
这个问题可以通过对每个闭区间的左端点进行排序，并从左到右选择左端点，直到下一个要选择的左端点与上一个选择的左端点之间的距离大于当前选择的左端点与上一个选择的左端点之间的距离为止。
5. 排班问题：给定一组员工和他们的班次需求，以及一组工作日的日程安排。
贪心算法需要为员工分配班次，以最小化总工作时间并满足所有工作日的需求。
这个问题可以通过从可用的班次中选择最长的班次，并从左到右分配员工，直到所有员工都被分配到一个班次为止。
这些问题是贪心算法的经典示例，它们展示了贪心算法在解决优化问题中的广泛应用。
贪心算法详解贪心算法思想：顾名思义，贪心算法总是作出在当前看来最好的选择。
也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。
当然，希望贪心算法得到的最终结果也是整体最优的。
虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。
如单源最短路经问题，最小生成树问题等。
在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。
贪心算法的基本要素：1.贪心选择性质。
所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。
这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。
动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。
对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。
2. 当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。
问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。
贪心算法的基本思路：从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。
当达到算法中的某一步不能再继续前进时，算法停止。
该算法存在问题：1. 不能保证求得的最后解是最佳的；2. 不能用来求最大或最小解问题；3. 只能求满足某些约束条件的可行解的范围。
实现该算法的过程：从问题的某一初始解出发；while 能朝给定总目标前进一步do求出可行解的一个解元素；由所有解元素组合成问题的一个可行解；用背包问题来介绍贪心算法：背包问题：有一个背包，背包容量是M=150。
有7个物品，物品可以分割成任意大小。
要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。
物品A B C D E F G重量35 30 60 50 40 10 25价值10 40 30 50 35 40 30分析如下目标函数：∑pi最大约束条件是装入的物品总重量不超过背包容量：∑wi<=M( M=150)。
算法实验报告范文《算法设计与分析》实验报告班级姓名学号年月日目录实验一二分查找程序实现…………………………………………………………………03页实验二棋盘覆盖问题（分治法）.…………………………………………………………08页实验三0-1背包问题的动态规划算法设计……………………………………………….11页实验四背包问题的贪心算法………………………………………………………………14页实验五最小重量机器设计问题（回溯法）………………………………………………17页实验六最小重量机器设计问题（分支限界法）…………………………………………20页指导教师对实验报告的评语成绩：指导教师签字：年月日2实验一：二分查找程序实现一、实验时间：2022年10月8日，星期二，第一、二节地点：J13#328二、实验目的及要求目的：1、用c/c++语言实现二分搜索算法。
2、通过随机产生有序表的方法，测出在平均意义下算法比较次数随问题规模的变化曲线，并作图。
三、实验环境平台：Win732位操作系统开发工具：Codeblock10.05四、实验内容对已经排好序的n个元素a[0：n-1]，现在要在这n个元素中找出一特定元素某。
五、算法描述及实验步骤算法描述：折半查找法也称为二分查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(logn)完成搜索任务。
它的基本思想是，将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的某作比较，如果某=a[n/2]则找到某，算法终止。
如果某a[n/2]，则我们只要在数组a的右半部继续搜索某。
二分搜索法的应用极其广泛，而且它的思想易于理解。
确定算法复杂度基本步骤：1、首先设定问题规模n；2、随即产生递增数列；3、在n个有序数中随机取一个作为待查找量，搜索之；4、记录查找过程中的比较次数，再次生成新的有序表并查找，记录查找次数，每个数组重复10次；5、改变问题规模n重复上述步骤2~4，n取100、200……1000；6、依实验数据作图，并与理论图作比较；7、二分搜索算法平均查找次数：问题规模为n时，平均查找次数为：A(n)=Int(logn)+1/2//Int()函数为向下取整3即二分搜索算法对于含有n个数据的有序表L平均作了约Int(logn)+1/2次的查找操作。
1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:_________,________,________,__________,__________。
2.算法的复杂性有_____________和___________之分，衡量一个算法好坏的标准是______________________。
3.某一问题可用动态规划算法求解的显著特征是____________________________________。
4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X 和Y的一个最长公共子序列_____________________________。
5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含___________。
6.动态规划算法的基本思想是将待求解问题分解成若干____________，先求解___________，然后从这些____________的解得到原问题的解。
7.以深度优先方式系统搜索问题解的算法称为_____________。
8.0-1背包问题的回溯算法所需的计算时间为_____________,用动态规划算法所需的计算时间为____________。
9.动态规划算法的两个基本要素是___________和___________。
10.二分搜索算法是利用_______________实现的算法。
二、综合题（50分）1.写出设计动态规划算法的主要步骤。
2.流水作业调度问题的johnson算法的思想。
3.若n=4，在机器M1和M2上加工作业i所需的时间分别为a i和b i，且(a1,a2,a3,a4)=(4,5,12,10)，(b1,b2,b3,b4)=(8,2,15,9)求4个作业的最优调度方案，并计算最优值。
4.使用回溯法解0/1背包问题：n=3，C=9，V={6,10,3}，W={3,4,4},其解空间有长度为3的0-1向量组成，要求用一棵完全二叉树表示其解空间（从根出发，左1右0），并画出其解空间树，计算其最优值及最优解。
湖南理工学院课程论文论文题目贪心法的应用课程名称算法设计与分析姓名学号专业计算机科学与技术年级学院计算机日期（2014年4月10日）课程论文评价标准贪心法的应用摘要：在解决问题的过程中，通过逐步获得最优解从而获得整体最优解的策略就是贪心策略，在已经学会在解的范围可以确定的情况下，可以采用枚举或递归策略，一一比较它们最后找到最优解；但当解的范围非常大时，枚举和递归的效率会非常低。
这时就可以考虑用贪心策略。
贪心算法没有固定的框架，算法设计的关键是贪心策略的选择，贪心策略要具有无后向性，即某阶段状态一旦确定以后，不受这个状态以后的策略的影响。
当一个问题有好几种解决方法时，贪心法应该是最好的选择之一。
本文讲述了贪心算法的含义、基本思路以及贪心算法在实例中的应用。
关键词：贪心算法；删数问题；最小生成树一、引言在平时解决问题的过程中，当一个问题就有无后向性和贪心选择性质时，贪心算法通常会给出一个简单、直观和高效的解法。
贪心算法通过一系列的选择来得到一个问题的解。
它所做的每一个选择都是当前状态下就有某种意义的最好选择，即贪心选择；并且每次贪心选择都能将问题化解为一个更小的与原问题具有相同形式的子问题。
尽管贪心算法对于很多问题不能总是产生整体最优解，但对于最短路径、最小生成树问题，以及删数问题等却可以获得整体最优解，而且所给出的算法一般比动态规划算法更为简单、直观和高效。
二、贪心算法的含义和特点（一）贪心算法的含义贪心算法是通过一系列的选择来得到问题解的过程。
贪心算法是一种能够得到某种度量意义下的最优解的分级处理方法，它总是做出在当前看来是最有的选择，也就是说贪心策略并不是从整体上加以考虑，它所做出的选择只是在某种意义上的局部最优解算法。
（二）贪心算法的特点1、从全局来看，运用贪心策略解决的问题在程序运行过程中无回溯过程，后面的每一步都是当前看似最佳的选择，这种选择依赖已作出的选择，但并不依赖未作出的选择。
2、不能保证最后求出的解是最佳的。
多背包问题近似解法及其近似⽐多背包问题：给定n个物品，其中物品i的价格是vi,重量是wi,有m个背包，背包j最⼤能装物品重量为Bj,求这些背包能够装下物品的最⾼价格，其中每个物品要么完全放⼊背包要么不放⼊。
(1),给出⼀个求解该问题的近似算法。
(2),设所有Bj都相等，分析你给出的算法的近似⽐。
这个问题到底有没有⾮近似的⽅法？这个是不是NP问题呢？虽然有些疑惑，但还是找出⼀个近似算法吧！(1),这⾥⽤贪⼼算法，依次从剩余的物品中⽤贪⼼算法使得第i个背包中的物品价值达到最⼤，i从1到m。
(2),这⾥我们可以证明这个近似算法具有常近似⽐。
设最优解的总价值为C*,我们要证明C*/C为常数, C为这个近似解的最⼤价值。
如果有背包没有物品的话，C*=C。
这⾥我们假设每个背包⾥都有物品。
假设物品可以部分放⼊背包，那么我们可以⽤⼀个贪⼼算法解决上⾯的优化问题，得到的解的最⼤价值为C', 每个背包j的容量为Wj'=B，价值为Vj'，那么C'>=C*。
⽅案(1)中，假设每个背包j的容量为Wj,所含物品价值为Vj，那么Vj/Wj >= Vj'/Wj'。
在⽅案（1）基础上，我们⽤单位价值为Vj/Wj的物品把背包j填满，最后物品的总价值为C'', 每个背包j的所含物品的重量为Wj''=B, Vj'', 那么Vj''/Wj'' = Vj/Wj >= Vj'/Wj'，所以C'' >= C'。
⼜有C'' <= kC，其中，k = B/min{wi}。
所以C* <= C' <= C'' <= kC, => C*/C <=k(常数)。
得证。
这⾥有⼀个更优的解法，近似⽐为2.。
（0-1）背包问题的解法小结1．动态规划法递推关系：– 考虑一个由前i 个物品(1≤i ≤n )定义的实例，物品的重量分别为w 1,…,w i ，价值分别为v 1，…，v i ，背包的承重量为j (1≤j ≤W )。
设V [I,j]为该实例的最优解的物品总价值– 分成两类子集：• 根据定义，在不包括第i 个物品的子集中，最优子集的价值是V [i -1,j ]• 在包括第i 个物品的子集中(因此，j －w ≥0)，最优子集是由该物品和前i -1个物品中能够放进承重量为i －w j 的背包的最优子集组成。
这种最忧子集的总价值等于v i +V [i -1,j -w i ].0]0,[时，0 当0;][0,时，0初始条件：当],1[}],1[],,1[max{],[=≥=≥<≥⎩⎨⎧-+---=i V i j V j w j w j j i V v w j i V j i V j i V i i i i以记忆功能为基础的算法：用自顶向下的方式对给定的问题求解，另外维护一个类似自底向上动态规划算法使用的表格。
一开始的时候，用一种“null”符号创始化表中所有的单元，用来表明它们还没有被计算过。
然后，一旦需要计算一个新的值，该方法先检查表中相应的单元：如果该单元不是“null ”，它就简单地从表中取值；否则，就使用递归调用进行计算，然后把返回的结果记录在表中。
算法 MFKnapsack(I,j)//对背包问题实现记忆功能方法//输入：一个非负整数i 指出先考虑的物品数量，一个非负整数j 指出了背包的承重量 //输出：前i 个物品的最伏可行子集的价值//注意：我们把输入数组Weights[1..n],Values[1..n]和表格V[0..n,0..W]作为全局变量，除了行0和列0用0初始化以外，V 的所有单元都用-1做初始化。
if V[I,j]<01if j<Weights[i]value ←MFKnapsack(i-1,j)elsevalue ←max(MFKnapsack(i-1),j), Value[i]+MFKnapsack(i-1,j-eights[i]))V[I,j]←valuereturn V[I,j]2．贪心算法1) 背包问题基本步骤：首先计算每种物品单位重量的价值Vi/Wi ，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。
背包问题算法导论课程设计一、课程目标知识目标：1. 理解背包问题的基础概念，掌握其定义和数学模型。
2. 学习并掌握贪心算法、动态规划算法解决0-1背包问题的基本原理和步骤。
3. 能够运用所学算法解决实际的背包问题，并对不同算法进行比较和分析。
技能目标：1. 培养学生的逻辑思维能力，使其能够运用算法思想解决实际问题。
2. 提高学生的编程能力，使其能够独立编写解决背包问题的程序代码。
3. 培养学生的团队协作能力，通过分组讨论和分享，共同解决复杂问题。
情感态度价值观目标：1. 培养学生对算法学习的兴趣，激发其探索精神和创新意识。
2. 引导学生树立正确的价值观，认识到算法在解决实际问题中的重要性。
3. 培养学生面对困难时的坚持和毅力，鼓励他们勇于挑战自我，克服困难。
本课程针对高中年级学生，结合背包问题算法的学科特点，旨在提高学生的逻辑思维和编程能力。
课程要求学生在掌握基本概念和算法原理的基础上，能够将所学知识应用于实际问题的解决。
通过本课程的学习，学生将能够具备解决类似问题的能力，并为后续学习更复杂的算法打下坚实基础。
二、教学内容1. 背包问题基本概念：介绍背包问题的定义、分类以及数学模型。
- 0-1背包问题- 完全背包问题- 多重背包问题2. 贪心算法：讲解贪心算法的基本原理，分析贪心算法在解决背包问题中的应用。
- 贪心策略的选择- 贪心算法的步骤及实现3. 动态规划算法：介绍动态规划的基本思想，分析动态规划在解决背包问题中的应用。
- 动态规划原理- 0-1背包问题的动态规划解法- 完全背包问题的动态规划解法4. 算法分析与比较：对不同算法进行时间复杂度和空间复杂度分析，比较各自的优缺点。
5. 实践环节：通过编程实践，让学生独立解决背包问题，并分组讨论、分享经验。
6. 拓展与提高：介绍其他解决背包问题的算法，如分支限界法等，拓展学生的知识面。
教学内容依据课程目标，紧密结合教材，按照教学大纲进行安排。
课程进度分为基础理论、算法分析与实践、拓展与提高三个阶段，以确保学生能够系统、科学地掌握背包问题算法的相关知识。
背包问题摘要：背包问题在信息加密、预算控制、项目选择、材料切割、货物装载、嘲络信息安全等应用中具有重要的价值。
从计算复杂性理论看，背包问题是一个经典NP 难解问题。
半个多世纪以来，该问题一直是算法与复杂性研究的热点问题之一。
论文研究了背包问题的实用求解算法，提出了改进的新算法，并利用Maltab 对几种算法进行了仿真实验，测试的结果显示出新算法在解决0／1背包问题时表现出了良好的性能。
关键字：蚁群算法，背包问题，遗传算法，MATLAB引言背包问题(knapsackproblem ，简称KP)是运筹学中一个典型的优化难题，在预算控制、项目选择、材料切割、货物装载等实践中有重要应用，并且还常常作为其他问题的子问题加以研究。
随着网络技术的不断发展，背包公钥密码在电子商务中的公钥设计中也起着重要的作用。
背包问题的数学模型为：Max ƒ（21,x x …n x ）＝j j nj x c 1=∑ 2,1=j …ｎt s . nj 1=∑ j j ij b x a ≤ 2,1=i …{}1,0⊆j i x m式中，n 为物品的编号：ｍ为资源的编号；j c 为第j 个物品的受益量；i b 成为第i 种资源的预算：ij a 为第ｊ个物品占用第i 种资源的量：j x 为o-1决策变量(当物品ｊ被选择时j x ＝１否贝j x =0)。
KP的语言描述可以这样：现有ｊ（ｊ=1，2，⋯，n)个物品，每个物品将会消耗m种资源啦a=（1，2，⋯，m)，如果将物品ｊ装人ij背包将会获益q，与此同时，要求所有装入背包的物品消耗的资源I 不能超过b。
i背包问题可以衍生出一系列与之相关的优化问题，如有限背包问题(物体可具有相同价值和重量但数量是有限的)，无限背包问题(具有相同价值和重量的物体数量可以是无限的)，多背包问题(将物体装入多个容量不同的背包)等。
本文中所指背包问题如无特殊说明，均指"Fl的简单0／1背包问题。
背包问题在实践中有广泛的应用背景。
列举用贪心算法求解的经典问题
1. 零钱兑换问题：给定一些面值不同的硬币和一个金额，要求用最少的硬币凑出这个金额。
2. 最小生成树问题：给定一个无向带权图，要求用最小的权值构建一棵生成树。
3. 背包问题：给定一些物品和一个背包，每个物品有对应的价值和重量，要求在背包容量限制下，选取物品使得总价值最大。
4. 活动安排问题：有若干个活动需要分配一段时间，每个活动有对应的开始时间和结束时间，要求选取尽可能多的活动，使得任两个安排的活动时间不重叠。
5. 单源最短路径问题：给定一个有向带权图和一个起始节点，要求求出从起始节点到其他所有节点的最短路径。
6. 任务调度问题：有若干个需要完成的任务和多个可执行任务的处理器，要求将任务分配给处理器，使得执行总时间最小。
7. 区间覆盖问题：给定一些区间，要求用尽可能少的区间覆盖整个线段。
8. 哈夫曼编码问题：给定一些字符及其对应的出现概率，要求用最短的编码方式表示这些字符。
贪心算法的应用课程名称：算法设计与分析院系：计算机科学与信息工程学院学生姓名：****学号：**********专业班级：********************************** 指导教师：******201312-27贪心算法的应用摘要：顾名思义，贪心算法总是作出在当前看来最好的选择。
也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。
当然，希望贪心算法得到的最终结果也是整体最优的。
虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。
如单源最短路经问题，最小生成树问题等。
在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。
贪心算法求问题一般具有两个重要性质：贪心选择性质和最优子结构性质。
所谓贪心选择性是指所求问题的整体最优解可以通过一系列局部最优解的选择，即贪心选择达到。
这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法主要区别。
当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。
问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。
背包问题是一个经典的问题，我们可以采用多种算法去求解0/1背包问题，比如动态规划法、分支限界法、贪心算法、回溯法。
在这里我们采用贪心法解决这个问题。
关键词：贪心法背包问题最优化目录第1章绪论 (3)1.1 贪心算法的背景知识 (3)1.2 贪心算法的前景意义 (3)第2章贪心算法的理论知识 (4)2.1 问题的模式 (4)2.2 贪心算法的一般性描述 (4)第3章背包问题 (5)3.1 问题描述 (5)3.2 问题分析 (5)3.3算法设计 (5)3.4 测试结果与分析 (10)第4章结论 (12)参考文献 (13)附件 (13)第1章绪论1.1 贪心算法的背景知识贪心算法又叫登山法，它的根本思想是逐步到达山顶，即逐步得最优解，是解决最优化问题时的一种简单但适用范围有限的策略。
贪心算法的例子
贪心算法是一种解决优化问题的算法，它通常用于在一组选择中作出最优决策。
在贪心算法中，每次选择都是当前状态下的最优解，而不考虑将来可能出现的情况。
下面是一些贪心算法的例子。
1. 零钱兑换问题
假设你有一些硬币，每个硬币的面值分别为1、5、10、50、100。
现在要找零n元，最少需要多少个硬币呢？在贪心算法中，我们每次选择最大面值的硬币，直到凑够n元为止。
2. 区间覆盖问题
假设你有一些区间，每个区间用起点和终点表示。
现在要用尽可能少的区间覆盖所有的点，怎么办？在贪心算法中，我们每次选择覆盖范围最大的区间，直到所有点都被覆盖为止。
3. 最小生成树问题
假设你有一个连通无向图，每条边都有一个权值。
现在要选择一些边，构成一棵树，使得总权值最小，怎么办？在贪心算法中，我们每次选择与当前树相连的边中，权值最小的边，直到所有点都被覆盖为止。
4. 背包问题
假设你有一个背包，容量为C，有一些物品，每个物品有重量w 和价值v。
现在要选择一些物品，放入背包中，使得总重量不超过C，总价值最大，怎么办？在贪心算法中，我们每次选择单位价值最大的物品，直到背包装满为止。
这些都是贪心算法的例子，贪心算法虽然看起来简单，但是它在某些情况下可以得到最优解，而且时间复杂度也比较低。
算法分析与设计大作业…实验题目：0-1背包问题求解方法综述组员：班级：指导老师：]%0-1背包问题求解方法综述【摘要】：0-1背包问题是一个经典的NP-hard组合优化问题，现实生活中的很多问题都可以以它为模型。
本文首先对背包问题做了阐述，然后用蛮力解法、动态规划算法、贪心算法和回溯解法对背包问题进行求解，分析了0-1背包问题的数学模型,刻划了最优解的结构特征,建立了求最优值的递归关系式。
最后对四种算法从不同角度进行了对比和总结。
【关键词】：0-1背包问题；蛮力解法；动态规划算法；贪心算法；回溯解法。
0.引言0-1背包问题是指给定n个物品,每个物品均有自己的价值vi和重量wi(i=1,2,…,n),再给定一个背包,其容量为W。
要求从n个物品中选出一部分物品装入背包,这部分物品的重量之和不超过背包的容量,且价值之和最大。
单个物品要么装入,要么不装入。
很多问题都可以抽象成该问题模型,如配载问题、物资调运[1]问题等,因此研究该问题具有较高的实际应用价值。
目前,解决0-1背包问题的方法有很多,主要有动态规划法、回溯法、分支限界法、遗传算法、粒子群算法、人工鱼群算法、蚁群算法、模拟退火算法、蜂群算法、禁忌搜索算法等。
其中动态规划、回溯法、分支限界法时间复杂性比较高,计算智能算法可能出现局部收敛,不一定能找出问题的最优解。
文中在动态规划法的基础上进行了改进,提出一种求解0-1背包问题的算法,该算法每一次执行总能得到问题的最优解,是确定性算法,算法的时间复杂性最坏可能为O(2n)。
背包问题描述0-1背包问题(KP01)是一个著名的组合优化问题。
它应用在许多实际领域,如项目选择、资源分布、投资决策等。
背包问题得名于如何选择最合适的物品放置于给定背包中。
本文主要研究背包问题中最基础的0/1背包问题的一些解决方法。
为解决背包问题，大量学者在过去的几十年中提出了很多解决方法。
解决背包问题的算法有最优算法和启发式算法[2]，最优算法包括穷举法、动态规划法、分支定界法、图论法等，启发式算法包括贪心算法、遗传算法、蚁群算法、粒子算法等一些智能算法。
实验五：贪心算法求解背包问题
实验内容
应用贪心算法求解离散背包问题，分析时间复杂度。
有一个承重为W的背包和n个物品，它们各自的重量和价值分别是wi和vi（1<=i<=n），设
求这些物品中最有价值的一个子集。如果每次选择某一个物品的时候，只能全部拿走，则这
一问题称为离散（0-1）背包问题；如果每次可以拿走某一物品的任意一部分，则这一问题
称为连续背包问题。
算法思想
• 动态规划的思想：
– 对较小的子问题进行一次求解，并把结果记录下来，然后利用较小问题的解，
求解出较大问题的解，直到求解出最大问题的解。
–
引进一个二维数组ch[MAX][MAX]，用ch[i][j]记录CH1与CH2的LCS 的长度，
b[i][j]记录ch[i][j]是通过哪一个子问题的值求得的，以决定搜索的方向。
我们是自底向上进行递推计算，那么在计算ch[i,j]之前，ch[i-1][j-1]，
ch[i-1][j]与ch[i][j-1]均已计算出来。此时我们根据CH1 [i] = CH2[j]还是
CH1[i] != CH2[j]，就可以计算出ch[i][j]。
算法
length(string CH1,string CH2,int b[MAX][MAX])
//用于构建动态数组
//输入：两字符窜
//输出：最长公共子序列
for(i=1;i<=ch1Len;i++)//二重循环求解
for(int j=1;j<=ch2Len;j++)
{
if(CH1[i-1]==CH2[j-1])//相等字符
{
ch[i][j]=ch[i-1][j-1]+1;
b[i][j]=0;
}
else if(ch[i-1][j]>=ch[i][j-1])//上比较大
{
ch[i][j]=ch[i-1][j];
b[i][j]=1;
}
else//左比较大
{
ch[i][j]=ch[i][j-1];
b[i][j]=-1;
}
}
printCS(int b[MAX][MAX],string x,int i,int j)
//回溯求出最长子序列输出
//输入：标记数组
//输出：最长子序列
if(i == 0 || j == 0)//边界，返回
return;
if(b[i][j] == 0)
{
printCS(b, x, i-1, j-1);//左上
cout<
else if(b[i][j] == 1)
printCS(b, x, i-1, j);//上
else
printCS(b, x, i, j-1);//左
源程序
//应用贪心算法求解离散背包问题
#include
using namespace std;
#define MAX 100
//结构体
struct Elem
{
double W;
double V;
double P;
int number;
};
//顺序表
struct SqList
{
Elem *elem;
int length;
int listsize;
};
//构造一个空的线性顺序表
void InitList_Sq(SqList &L)
{
L.elem=(Elem *)malloc(100*sizeof(Elem));
L.length=0;
L.listsize=100;
}
//********************************
//构造背包,顺序表
//******************************
void input(SqList &L)
{
cout<<"请输入物品的个数：";
cin>>L.length;
for(int i=0;i
cout<<"请输入第"<
L.elem[i].P=L.elem[i].V/L.elem[i].W;
cout<<"价值比为："<
}
}
//*********************************
//插入排序由大到小
//*******************************
void inser(SqList &L)
{
Elem inserter;
int index;//inserter待插入合适位置的元素,index指示插入位置
for(int pass=1;pass
index=pass-1;
while(index>=0&&inserter.P>L.elem[index].P){ //寻找插入位置
L.elem[index+1]=L.elem[index];
index--; //指针前移，再比较
}
L.elem[index+1]=inserter;//跳出while时，找到插入位置
}//end of for
cout<<"按照价值比由大到小排列的顺序为：";
for(pass=0;pass
//*************************************************8
//背包程序
//采用贪心算法
//根据价值和重量的比来实现贪心算法
//************************************************
void bag(SqList L)
{
double w,sumV=0,sumW=0;
int list[MAX],a=0;
cout<<"请输入背包承重量W:";
cin>>w;
inser(L);
for(int i=0;i
while(sumW+L.elem[i].W<=w)
{
sumW=sumW+L.elem[i].W;
sumV=sumV+L.elem[i].V;
list[a++]=L.elem[i].number;
}
}
cout<<"最后包里的总重量为："<
for(i=0;i
cout<
}
int main()
{
cout<<"贪心算法求解背包问题"<
InitList_Sq(L);
input(L);
bag(L);
return 0;
}
实验结论
1、 运行截图
查找最长公共子序列长度时的动态规划两个for循环，时间复杂度为
Ｏ（ｎ＊ｎ）。在回溯查找时，由于每次调用至少向上或向左（或向
上向左同时）移动一步，故最多调用(m + n)次就会遇到i = 0或j = 0
的情况，此时开始返回。返回时与递归调用时方向相反，步数相同，
故算法时间复杂度为Θ(m + n)。
