下载文档原格式
贪心算法是一种在解决问题的过程中追求局部最优的算法，对于一个有多种属性的事物来说，贪心算法会优先满足某种条件，追求局部最优的同时希望达到整体最优的效果。
以下是一些经典的贪心算法问题：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.。
实验五：贪心算法求解背包问题
实验内容
应用贪心算法求解离散背包问题，分析时间复杂度。
有一个承重为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)。
