2023年8月1日发(作者：)

c语⾔贪⼼算法背包问题_⼀起攻克贪⼼算法01基本概念贪⼼算法是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，只做出在某种意义上的局部最优解。贪⼼算法不是对所有问题都能得到整体最优解，关键是贪⼼策略的选择，选择的贪⼼策略必须具备⽆后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。贪⼼算法没有固定的算法框架，算法设计的关键是贪⼼策略的选择。必须注意的是，贪⼼算法不是对所有问题都能得到整体最优解，选择的贪⼼策略必须具备⽆后效性(即某个状态以后的过程不会影响以前的状态，只与当前状态有关。)所以，对所采⽤的贪⼼策略⼀定要仔细分析其是否满⾜⽆后效性。02贪⼼算法的基本思路解题的⼀般步骤是：1.建⽴数学模型来描述问题；2.把求解的问题分成若⼲个⼦问题；3.对每⼀⼦问题求解，得到⼦问题的局部最优解；4.把⼦问题的局部最优解合成原来问题的⼀个解。03该算法存在的问题不能保证求得的最后解是最佳的不能⽤来求最⼤值或最⼩值的问题只能求满⾜某些约束条件的可⾏解的范围04贪⼼算法适⽤的问题贪⼼策略适⽤的前提是：局部最优策略能导致产⽣全局最优解。实际上，贪⼼算法适⽤的情况很少。⼀般对⼀个问题分析是否适⽤于贪⼼算法，可以先选择该问题下的⼏个实际数据进⾏分析，就可以做出判断。05贪⼼选择性质所谓贪⼼选择性质是指所求问题的整体最优解可以通过⼀系列局部最优的选择，换句话说，当考虑做何种选择的时候，我们只考虑对当前问题最佳的选择⽽不考虑⼦问题的结果。这是贪⼼算法可⾏的第⼀个基本要素。贪⼼算法以迭代的⽅式作出相继的贪⼼选择，每作⼀次贪⼼选择就将所求问题简化为规模更⼩的⼦问题。对于⼀个具体问题，要确定它是否具有贪⼼选择性质，必须证明每⼀步所作的贪⼼选择最终导致问题的整体最优解。当⼀个问题的最优解包含其⼦问题的最优解时，称此问题具有最优⼦结构性质。问题的最优⼦结构性质是该问题可⽤贪⼼算法求解的关键特征。06贪⼼算法的实现框架从问题的某⼀初始解出发：while (朝给定总⽬标前进⼀步){ 利⽤可⾏的决策，求出可⾏解的⼀个解元素。}由所有解元素组合成问题的⼀个可⾏解；07例题分析如果⼤家⽐较了解动态规划，就会发现它们之间的相似之处。最优解问题⼤部分都可以拆分成⼀个个的⼦问题，把解空间的遍历视作对⼦问题树的遍历，则以某种形式对树整个的遍历⼀遍就可以求出最优解，⼤部分情况下这是不可⾏的。贪⼼算法和动态规划本质上是对⼦问题树的⼀种修剪，两种算法要求问题都具有的⼀个性质就是⼦问题最优性(组成最优解的每⼀个⼦问题的解，对于这个⼦问题本⾝肯定也是最优的)。动态规划⽅法代表了这⼀类问题的⼀般解法，我们⾃底向上构造⼦问题的解，对每⼀个⼦树的根，求出下⾯每⼀个叶⼦的值，并且以其中的最优值作为⾃⾝的值，其它的值舍弃。⽽贪⼼算法是动态规划⽅法的⼀个特例，可以证明每⼀个⼦树的根的值不取决于下⾯叶⼦的值，⽽只取决于当前问题的状况。换句话说，不需要知道⼀个节点所有⼦树的情况，就可以求出这个节点的值。由于贪⼼算法的这个特性，它对解空间树的遍历不需要⾃底向上，⽽只需要⾃根开始，选择最优的路，⼀直⾛到底就可以了。话不多说，我们来看⼏个具体的例⼦慢慢理解它： 1.活动选择问题

这是《算法导论》上的例⼦，也是⼀个⾮常经典的问题。有n个需要在同⼀天使⽤同⼀个教室的活动a1,a2,…,an，教室同⼀时刻只能由⼀个活动使⽤。每个活动ai都有⼀个开始时间si和结束时间fi 。⼀旦被选择后，活动ai就占据半开时间区间[si,fi)。如果[si,fi]和[sj,fj]互不重叠，ai和aj两个活动就可以被安排在这⼀天。该问题就是要安排这些活动使得尽量多的活动能不冲突的举⾏。例如下图所⽰的活动集合S，其中各项活动按照结束时间单调递增排序。考虑使⽤贪⼼算法的解法。为了⽅便，我们⽤不同颜⾊的线条代表每个活动，线条的长度就是活动所占据的时间段，蓝⾊的线条表⽰我们已经选择的活动；红⾊的线条表⽰我们没有选择的活动。如果我们每次都选择开始时间最早的活动，不能得到最优解：如果我们每次都选择持续时间最短的活动，不能得到最优解：可以⽤数学归纳法证明，我们的贪⼼策略应该是每次选取结束时间最早的活动。直观上也很好理解，按这种⽅法选择相容活动为未安排活动留下尽可能多的时间。这也是把各项活动按照结束时间单调递增排序的原因。#include#include#includeusing namespace std; int N;struct Act{ int start; int end;}act[100010];bool cmp(Act a,Act b) { return }int greedy_activity_selecto2.钱币找零问题

这个问题在我们的⽇常⽣活中就更加普遍了。假设1元、2元、5元、10元、20元、50元、100元的纸币分别有c0, c1, c2, c3, c4, c5,c6张。现在要⽤这些钱来⽀付K元，⾄少要⽤多少张纸币？⽤贪⼼算法的思想，很显然，每⼀步尽可能⽤⾯值⼤的纸币即可。在⽇常⽣活中我们⾃然⽽然也是这么做的。在程序中已经事先将Value按照从⼩到⼤的顺序排好。#include#includeusing namespace std;const int N=7;int Count[N]={3,0,2,1,0,3,5};int Value[N]={1,2,5,10,20,50,100};int solve(int money){ int num=0; for(int i=N-1;i3.再论背包问题

在从零开始学动态规划中我们已经谈过三种最基本的背包问题：零⼀背包，部分背包，完全背包。很容易证明，背包问题不能使⽤贪⼼算法。然⽽我们考虑这样⼀种背包问题：在选择物品i装⼊背包时，可以选择物品的⼀部分，⽽不⼀定要全部装⼊背包。这时便可以使⽤贪⼼算法求解了。计算每种物品的单位重量价值作为贪⼼选择的依据指标，选择单位重量价值最⾼的物品，将尽可能多的该物品装⼊背包，依此策略⼀直地进⾏下去，直到背包装满为⽌。在零⼀背包问题中贪⼼选择之所以不能得到最优解原因是贪⼼选择⽆法保证最终能将背包装满，部分闲置的背包空间使每公⽄背包空间的价值降低了。在程序中已经事先将单位重量价值按照从⼤到⼩的顺序排好。#includeusing namespace std; const int N=4; void knapsack(float M,float v[],float w[],float x[]); int main() { float M=50; //背包所能容纳的重量 float w[]={4.多机调度问题

n个作业组成的作业集，可由m台相同机器加⼯处理。要求给出⼀种作业调度⽅案，使所给的n个作业在尽可能短的时间内由m台机器加⼯处理完成。作业不能拆分成更⼩的⼦作业；每个作业均可在任何⼀台机器上加⼯处理。这个问题是NP完全问题，还没有有效的解法(求最优解)，但是可以⽤贪⼼选择策略设计出较好的近似算法(求次优解)。当n<=m时，只要将作业时间区间分配给作业即可；当n>m时，⾸先将n个作业从⼤到⼩排序，然后依此顺序将作业分配给空闲的处理机。也就是说从剩下的作业中，选择需要处理时间最长的，然后依次选择处理时间次长的，直到所有的作业全部处理完毕，或者机器不能再处理其他作业为⽌。如果我们每次是将需要处理时间最短的作业分配给空闲的机器，那么可能就会出现其它所有作业都处理完了只剩所需时间最长的作业在处理的情况，这样势必效率较低。在下⾯的代码中没有讨论n和m的⼤⼩关系，把这两种情况合⼆为⼀了。#include#includeusing namespace std; int speed[10010]; int mintime[110]; bool cmp( const int &x,const int &y) { return x>y; } int main() { int n,m;

5.⼩船过河问题

POJ1700是⼀道经典的贪⼼算法例题。题⽬⼤意是只有⼀艘船，能乘2⼈，船的运⾏速度为2⼈中较慢⼀⼈的速度，过去后还需⼀个⼈把船划回来，问把n个⼈运到对岸，最少需要多久。先将所有⼈过河所需的时间按照升序排序，我们考虑把单独过河所需要时间最多的两个旅⾏者送到对岸去，有两种⽅式：1.最快的和次快的过河，然后最快的将船划回来；次慢的和最慢的过河，然后次快的将船划回来，所需时间为：t[0]+2*t[1]+t[n-1]；2.最快的和最慢的过河，然后最快的将船划回来，最快的和次慢的过河，然后最快的将船划回来，所需时间为：2*t[0]+t[n-2]+t[n-1]。算⼀下就知道，除此之外的其它情况⽤的时间⼀定更多。每次都运送耗时最长的两⼈⽽不影响其它⼈，问题具有贪⼼⼦结构的性质。AC代码：#include#includeusing namespace std;int main(){ int a[1000],t,n,sum; scanf("%d",&t); while(t--) { scanf("%d",&n); sum=0; for(int i=0;iscanf( while(n>3)

6.区间覆盖问题

POJ1328是⼀道经典的贪⼼算法例题。题⽬⼤意是假设海岸线是⼀条⽆限延伸的直线。陆地在海岸线的⼀侧，⽽海洋在另⼀侧。每⼀个⼩的岛屿是海洋上的⼀个点。雷达坐落于海岸线上，只能覆盖d距离，所以如果⼩岛能够被覆盖到的话，它们之间的距离最多为d。题⽬要求计算出能够覆盖给出的所有岛屿的最少雷达数⽬。对于每个⼩岛，我们可以计算出⼀个雷达所在位置的区间。问题转化为如何⽤尽可能少的点覆盖这些区间。先将所有区间按照左端点⼤⼩排序，初始时需要⼀个点。如果两个区间相交⽽不重合，我们什么都不需要做；如果⼀个区间完全包含于另外⼀个区间，我们需要更新区间的右端点；如果两个区间不相交，我们需要增加点并更新右端点。AC代码：#include#include#includeusing namespace std;struct Point{ double x; double y;}point[1000];int cmp(const void *a, const void *b){ return (*(Point *)a).x>(*(Point *)7.销售⽐赛

在学校OJ上做的⼀道⽐较好的题，这⾥码⼀下。假设有偶数天，要求每天必须买⼀件物品或者卖⼀件物品，只能选择⼀种操作并且不能不选，开始⼿上没有这种物品。现在给你每天的物品价格表，要求计算最⼤收益。⾸先要明⽩，第⼀天必须买，最后⼀天必须卖，并且最后⼿上没有物品。那么除了第⼀天和最后⼀天之外我们每次取两天，⼩的买⼤的卖，并且把卖的价格放进⼀个最⼩堆。如果买的价格⽐堆顶还⼤，就交换。这样我们保证了卖的价格总是⼤于买的价格，⼀定能取得最⼤收益。#include#include#include#include#include#include#includeusing namespace std;long long int price[100010],t,n,res;int main(){ ios::sync_with_stdio(false); cin>>t;下⾯我们结合数据结构中的知识讲解⼏个例⼦。 n编码

这同样是《算法导论》上的例⼦。Huffman编码是⼴泛⽤于数据⽂件压缩的⼗分有效的编码⽅法。我们可以有多种⽅式表⽰⽂件中的信息，如果⽤01串表⽰字符，采⽤定长编码表⽰，则需要3位表⽰⼀个字符，整个⽂件编码需要300000位；采⽤变长编码表⽰，给频率⾼的字符较短的编码，频率低的字符较长的编码，达到整体编码减少的⽬的，则整个⽂件编码需要(45×1+13×3+12×3+16×3+9×4+5×4)×1000=224000位，由此可见，变长码⽐定长码⽅案好，总码长减⼩约25%。对每⼀个字符规定⼀个01串作为其代码，并要求任⼀字符的代码都不是其他字符代码的前缀，这种编码称为前缀码。可能⽆前缀码是⼀个更好的名字，但是前缀码是⼀致认可的标准术语。编码的前缀性质可以使译码⾮常简单：例如001011101可以唯⼀的分解为0,0,101,1101，因⽽其译码为aabe。译码过程需要⽅便的取出编码的前缀，为此可以⽤⼆叉树作为前缀码的数据结构：树叶表⽰给定字符；从树根到树叶的路径当作该字符的前缀码；代码中每⼀位的0或1分别作为指⽰某节点到左⼉⼦或右⼉⼦的路标。从上图可以看出，最优前缀编码码的⼆叉树总是⼀棵完全⼆叉树，⽽定长编码的⼆叉树不是⼀棵完全⼆叉树。给定编码字符集C及频率分布f，C的⼀个前缀码编码⽅案对应于⼀棵⼆叉树T。字符c在树T中的深度记为dT(c)，dT(c)也是字符c的前缀码长。则平均码长定义为：使平均码长达到最⼩的前缀码编码⽅案称为C的最优前缀码。

Huffman编码的构造⽅法：先合并最⼩频率的2个字符对应的⼦树，计算合并后的⼦树的频率；重新排序各个⼦树；对上述排序后的⼦树序列进⾏合并；重复上述过程，将全部结点合并成1棵完整的⼆叉树；对⼆叉树中的边赋予0、1，得到各字符的变长编码。POJ3253⼀道就是利⽤这⼀思想的典型例题。题⽬⼤意是有把⼀块⽆限长的⽊板锯成⼏块给定长度的⼩⽊板，每次锯都需要⼀定费⽤，费⽤就是当前锯的⽊板的长度。给定各个要求的⼩⽊板的长度以及⼩⽊板的个数，求最⼩的费⽤。以要求3块长度分别为5,8,5的⽊板为例：先从⽆限长的⽊板上锯下长度为21的⽊板，花费21；再从长度为21的⽊板上锯下长度为5的⽊板，花费5；再从长度为16的⽊板上锯下长度为8的⽊板，花费8；总花费=21+5+8=34。利⽤Huffman思想，要使总费⽤最⼩，那么每次只选取最⼩长度的两块⽊板相加，再把这些和累加到总费⽤中即可。为了提⾼效率，使⽤优先队列优化，并且还要注意使⽤long long int保存结果。AC代码：#include#include#includeusing namespace std;int main(){ long long int sum; int i,n,t,a,b; while(~scanf("%d",&n)) { priority_queue,greater >ra算法

Dijkstra算法是由ra于1959年提出，是⽬前公认的最好的求解最短路径的⽅法，使⽤的条件是图中不能存在负边。算法解决的是单个源点到其他顶点的最短路径问题，其主要特点是每次迭代时选择的下⼀个顶点是标记点之外距离源点最近的顶点，简单的说就是bfs+贪⼼算法的思想。#include#include#define INF 1000#define MAX_V 100using namespace std; int main(){ int V,E; int i,j,m,n; int cost[MAX_V][MAX_V]; int d[MAX_V]; bool used[M10.最⼩⽣成树算法

设⼀个⽹络表⽰为⽆向连通带权图G =(V, E) , E中每条边(v,w)的权为c[v][w]。如果G的⼦图G’是⼀棵包含G的所有顶点的树，则称G’为G的⽣成树。⽣成树的代价是指⽣成树上各边权的总和，在G的所有⽣成树中，耗费最⼩的⽣成树称为G的最⼩⽣成树。例如在设计通信⽹络时，⽤图的顶点表⽰城市，⽤边(v,w)的权c[v][w]表⽰建⽴城市v和城市w之间的通信线路所需的费⽤，最⼩⽣成树给出建⽴通信⽹络的最经济⽅案。构造最⼩⽣成树的Kruskal算法和Prim算法都利⽤了MST(最⼩⽣成树)性质：设顶点集U是V的真⼦集(可以任意选取)，如果(u,v)∈E为横跨点集U和V—U的边，即u∈U，v∈V- U，并且在所有这样的边中，(u,v)的权c[u][v]最⼩，则⼀定存在G的⼀棵最⼩⽣成树，它以(u,v)为其中⼀条边。使⽤反证法可以很简单的证明此性质。假设对G的任意⼀个最⼩⽣成树T，针对点集U和V—U，(u,v)∈E为横跨这2个点集的最⼩权边，T不包含该最⼩权边，但T包括节点u和v。将添加到树T中，树T将变为含回路的⼦图，并且该回路上有⼀条不同于的边,u’∈U,v’∈V-U。将删去，得到另⼀个树T’，即树T’是通过将T中的边替换为得到的。由于这2条边的耗费满⾜c[u][v]≤c[u’][v’]，故即T’耗费≤T的耗费，这与T是任意最⼩⽣成树的假设相⽭盾，从⽽得证。Prim算法每⼀步都选择连接U和V-U的权值最⼩的边加⼊⽣成树。#include#include#define MAX_V 100#define INF 1000using namespace std; int main(){ int V,E; int i,j,m,n; int cost[MAX_V][MAX_V]; int mincost[MAX_V]; bool

Kruskal算法每⼀步直接将权值最⼩的不成环的边加⼊⽣成树，我们借助并查集这⼀数据结构可以完美实现它。#include#include#define MAX_E 100using namespace std; struct edge{ int u,v,cost; };int pre[MAX_E];edge es[MAX_E];int find(int x);void initvalue(int x);bool sa

2023年8月1日发(作者：)

c语⾔贪⼼算法背包问题_⼀起攻克贪⼼算法01基本概念贪⼼算法是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，只做出在某种意义上的局部最优解。贪⼼算法不是对所有问题都能得到整体最优解，关键是贪⼼策略的选择，选择的贪⼼策略必须具备⽆后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。贪⼼算法没有固定的算法框架，算法设计的关键是贪⼼策略的选择。必须注意的是，贪⼼算法不是对所有问题都能得到整体最优解，选择的贪⼼策略必须具备⽆后效性(即某个状态以后的过程不会影响以前的状态，只与当前状态有关。)所以，对所采⽤的贪⼼策略⼀定要仔细分析其是否满⾜⽆后效性。02贪⼼算法的基本思路解题的⼀般步骤是：1.建⽴数学模型来描述问题；2.把求解的问题分成若⼲个⼦问题；3.对每⼀⼦问题求解，得到⼦问题的局部最优解；4.把⼦问题的局部最优解合成原来问题的⼀个解。03该算法存在的问题不能保证求得的最后解是最佳的不能⽤来求最⼤值或最⼩值的问题只能求满⾜某些约束条件的可⾏解的范围04贪⼼算法适⽤的问题贪⼼策略适⽤的前提是：局部最优策略能导致产⽣全局最优解。实际上，贪⼼算法适⽤的情况很少。⼀般对⼀个问题分析是否适⽤于贪⼼算法，可以先选择该问题下的⼏个实际数据进⾏分析，就可以做出判断。05贪⼼选择性质所谓贪⼼选择性质是指所求问题的整体最优解可以通过⼀系列局部最优的选择，换句话说，当考虑做何种选择的时候，我们只考虑对当前问题最佳的选择⽽不考虑⼦问题的结果。这是贪⼼算法可⾏的第⼀个基本要素。贪⼼算法以迭代的⽅式作出相继的贪⼼选择，每作⼀次贪⼼选择就将所求问题简化为规模更⼩的⼦问题。对于⼀个具体问题，要确定它是否具有贪⼼选择性质，必须证明每⼀步所作的贪⼼选择最终导致问题的整体最优解。当⼀个问题的最优解包含其⼦问题的最优解时，称此问题具有最优⼦结构性质。问题的最优⼦结构性质是该问题可⽤贪⼼算法求解的关键特征。06贪⼼算法的实现框架从问题的某⼀初始解出发：while (朝给定总⽬标前进⼀步){ 利⽤可⾏的决策，求出可⾏解的⼀个解元素。}由所有解元素组合成问题的⼀个可⾏解；07例题分析如果⼤家⽐较了解动态规划，就会发现它们之间的相似之处。最优解问题⼤部分都可以拆分成⼀个个的⼦问题，把解空间的遍历视作对⼦问题树的遍历，则以某种形式对树整个的遍历⼀遍就可以求出最优解，⼤部分情况下这是不可⾏的。贪⼼算法和动态规划本质上是对⼦问题树的⼀种修剪，两种算法要求问题都具有的⼀个性质就是⼦问题最优性(组成最优解的每⼀个⼦问题的解，对于这个⼦问题本⾝肯定也是最优的)。动态规划⽅法代表了这⼀类问题的⼀般解法，我们⾃底向上构造⼦问题的解，对每⼀个⼦树的根，求出下⾯每⼀个叶⼦的值，并且以其中的最优值作为⾃⾝的值，其它的值舍弃。⽽贪⼼算法是动态规划⽅法的⼀个特例，可以证明每⼀个⼦树的根的值不取决于下⾯叶⼦的值，⽽只取决于当前问题的状况。换句话说，不需要知道⼀个节点所有⼦树的情况，就可以求出这个节点的值。由于贪⼼算法的这个特性，它对解空间树的遍历不需要⾃底向上，⽽只需要⾃根开始，选择最优的路，⼀直⾛到底就可以了。话不多说，我们来看⼏个具体的例⼦慢慢理解它： 1.活动选择问题

这是《算法导论》上的例⼦，也是⼀个⾮常经典的问题。有n个需要在同⼀天使⽤同⼀个教室的活动a1,a2,…,an，教室同⼀时刻只能由⼀个活动使⽤。每个活动ai都有⼀个开始时间si和结束时间fi 。⼀旦被选择后，活动ai就占据半开时间区间[si,fi)。如果[si,fi]和[sj,fj]互不重叠，ai和aj两个活动就可以被安排在这⼀天。该问题就是要安排这些活动使得尽量多的活动能不冲突的举⾏。例如下图所⽰的活动集合S，其中各项活动按照结束时间单调递增排序。考虑使⽤贪⼼算法的解法。为了⽅便，我们⽤不同颜⾊的线条代表每个活动，线条的长度就是活动所占据的时间段，蓝⾊的线条表⽰我们已经选择的活动；红⾊的线条表⽰我们没有选择的活动。如果我们每次都选择开始时间最早的活动，不能得到最优解：如果我们每次都选择持续时间最短的活动，不能得到最优解：可以⽤数学归纳法证明，我们的贪⼼策略应该是每次选取结束时间最早的活动。直观上也很好理解，按这种⽅法选择相容活动为未安排活动留下尽可能多的时间。这也是把各项活动按照结束时间单调递增排序的原因。#include#include#includeusing namespace std; int N;struct Act{ int start; int end;}act[100010];bool cmp(Act a,Act b) { return }int greedy_activity_selecto2.钱币找零问题

这个问题在我们的⽇常⽣活中就更加普遍了。假设1元、2元、5元、10元、20元、50元、100元的纸币分别有c0, c1, c2, c3, c4, c5,c6张。现在要⽤这些钱来⽀付K元，⾄少要⽤多少张纸币？⽤贪⼼算法的思想，很显然，每⼀步尽可能⽤⾯值⼤的纸币即可。在⽇常⽣活中我们⾃然⽽然也是这么做的。在程序中已经事先将Value按照从⼩到⼤的顺序排好。#include#includeusing namespace std;const int N=7;int Count[N]={3,0,2,1,0,3,5};int Value[N]={1,2,5,10,20,50,100};int solve(int money){ int num=0; for(int i=N-1;i3.再论背包问题

在从零开始学动态规划中我们已经谈过三种最基本的背包问题：零⼀背包，部分背包，完全背包。很容易证明，背包问题不能使⽤贪⼼算法。然⽽我们考虑这样⼀种背包问题：在选择物品i装⼊背包时，可以选择物品的⼀部分，⽽不⼀定要全部装⼊背包。这时便可以使⽤贪⼼算法求解了。计算每种物品的单位重量价值作为贪⼼选择的依据指标，选择单位重量价值最⾼的物品，将尽可能多的该物品装⼊背包，依此策略⼀直地进⾏下去，直到背包装满为⽌。在零⼀背包问题中贪⼼选择之所以不能得到最优解原因是贪⼼选择⽆法保证最终能将背包装满，部分闲置的背包空间使每公⽄背包空间的价值降低了。在程序中已经事先将单位重量价值按照从⼤到⼩的顺序排好。#includeusing namespace std; const int N=4; void knapsack(float M,float v[],float w[],float x[]); int main() { float M=50; //背包所能容纳的重量 float w[]={4.多机调度问题

n个作业组成的作业集，可由m台相同机器加⼯处理。要求给出⼀种作业调度⽅案，使所给的n个作业在尽可能短的时间内由m台机器加⼯处理完成。作业不能拆分成更⼩的⼦作业；每个作业均可在任何⼀台机器上加⼯处理。这个问题是NP完全问题，还没有有效的解法(求最优解)，但是可以⽤贪⼼选择策略设计出较好的近似算法(求次优解)。当n<=m时，只要将作业时间区间分配给作业即可；当n>m时，⾸先将n个作业从⼤到⼩排序，然后依此顺序将作业分配给空闲的处理机。也就是说从剩下的作业中，选择需要处理时间最长的，然后依次选择处理时间次长的，直到所有的作业全部处理完毕，或者机器不能再处理其他作业为⽌。如果我们每次是将需要处理时间最短的作业分配给空闲的机器，那么可能就会出现其它所有作业都处理完了只剩所需时间最长的作业在处理的情况，这样势必效率较低。在下⾯的代码中没有讨论n和m的⼤⼩关系，把这两种情况合⼆为⼀了。#include#includeusing namespace std; int speed[10010]; int mintime[110]; bool cmp( const int &x,const int &y) { return x>y; } int main() { int n,m;

5.⼩船过河问题

POJ1700是⼀道经典的贪⼼算法例题。题⽬⼤意是只有⼀艘船，能乘2⼈，船的运⾏速度为2⼈中较慢⼀⼈的速度，过去后还需⼀个⼈把船划回来，问把n个⼈运到对岸，最少需要多久。先将所有⼈过河所需的时间按照升序排序，我们考虑把单独过河所需要时间最多的两个旅⾏者送到对岸去，有两种⽅式：1.最快的和次快的过河，然后最快的将船划回来；次慢的和最慢的过河，然后次快的将船划回来，所需时间为：t[0]+2*t[1]+t[n-1]；2.最快的和最慢的过河，然后最快的将船划回来，最快的和次慢的过河，然后最快的将船划回来，所需时间为：2*t[0]+t[n-2]+t[n-1]。算⼀下就知道，除此之外的其它情况⽤的时间⼀定更多。每次都运送耗时最长的两⼈⽽不影响其它⼈，问题具有贪⼼⼦结构的性质。AC代码：#include#includeusing namespace std;int main(){ int a[1000],t,n,sum; scanf("%d",&t); while(t--) { scanf("%d",&n); sum=0; for(int i=0;iscanf( while(n>3)

6.区间覆盖问题

POJ1328是⼀道经典的贪⼼算法例题。题⽬⼤意是假设海岸线是⼀条⽆限延伸的直线。陆地在海岸线的⼀侧，⽽海洋在另⼀侧。每⼀个⼩的岛屿是海洋上的⼀个点。雷达坐落于海岸线上，只能覆盖d距离，所以如果⼩岛能够被覆盖到的话，它们之间的距离最多为d。题⽬要求计算出能够覆盖给出的所有岛屿的最少雷达数⽬。对于每个⼩岛，我们可以计算出⼀个雷达所在位置的区间。问题转化为如何⽤尽可能少的点覆盖这些区间。先将所有区间按照左端点⼤⼩排序，初始时需要⼀个点。如果两个区间相交⽽不重合，我们什么都不需要做；如果⼀个区间完全包含于另外⼀个区间，我们需要更新区间的右端点；如果两个区间不相交，我们需要增加点并更新右端点。AC代码：#include#include#includeusing namespace std;struct Point{ double x; double y;}point[1000];int cmp(const void *a, const void *b){ return (*(Point *)a).x>(*(Point *)7.销售⽐赛

在学校OJ上做的⼀道⽐较好的题，这⾥码⼀下。假设有偶数天，要求每天必须买⼀件物品或者卖⼀件物品，只能选择⼀种操作并且不能不选，开始⼿上没有这种物品。现在给你每天的物品价格表，要求计算最⼤收益。⾸先要明⽩，第⼀天必须买，最后⼀天必须卖，并且最后⼿上没有物品。那么除了第⼀天和最后⼀天之外我们每次取两天，⼩的买⼤的卖，并且把卖的价格放进⼀个最⼩堆。如果买的价格⽐堆顶还⼤，就交换。这样我们保证了卖的价格总是⼤于买的价格，⼀定能取得最⼤收益。#include#include#include#include#include#include#includeusing namespace std;long long int price[100010],t,n,res;int main(){ ios::sync_with_stdio(false); cin>>t;下⾯我们结合数据结构中的知识讲解⼏个例⼦。 n编码

这同样是《算法导论》上的例⼦。Huffman编码是⼴泛⽤于数据⽂件压缩的⼗分有效的编码⽅法。我们可以有多种⽅式表⽰⽂件中的信息，如果⽤01串表⽰字符，采⽤定长编码表⽰，则需要3位表⽰⼀个字符，整个⽂件编码需要300000位；采⽤变长编码表⽰，给频率⾼的字符较短的编码，频率低的字符较长的编码，达到整体编码减少的⽬的，则整个⽂件编码需要(45×1+13×3+12×3+16×3+9×4+5×4)×1000=224000位，由此可见，变长码⽐定长码⽅案好，总码长减⼩约25%。对每⼀个字符规定⼀个01串作为其代码，并要求任⼀字符的代码都不是其他字符代码的前缀，这种编码称为前缀码。可能⽆前缀码是⼀个更好的名字，但是前缀码是⼀致认可的标准术语。编码的前缀性质可以使译码⾮常简单：例如001011101可以唯⼀的分解为0,0,101,1101，因⽽其译码为aabe。译码过程需要⽅便的取出编码的前缀，为此可以⽤⼆叉树作为前缀码的数据结构：树叶表⽰给定字符；从树根到树叶的路径当作该字符的前缀码；代码中每⼀位的0或1分别作为指⽰某节点到左⼉⼦或右⼉⼦的路标。从上图可以看出，最优前缀编码码的⼆叉树总是⼀棵完全⼆叉树，⽽定长编码的⼆叉树不是⼀棵完全⼆叉树。给定编码字符集C及频率分布f，C的⼀个前缀码编码⽅案对应于⼀棵⼆叉树T。字符c在树T中的深度记为dT(c)，dT(c)也是字符c的前缀码长。则平均码长定义为：使平均码长达到最⼩的前缀码编码⽅案称为C的最优前缀码。

Huffman编码的构造⽅法：先合并最⼩频率的2个字符对应的⼦树，计算合并后的⼦树的频率；重新排序各个⼦树；对上述排序后的⼦树序列进⾏合并；重复上述过程，将全部结点合并成1棵完整的⼆叉树；对⼆叉树中的边赋予0、1，得到各字符的变长编码。POJ3253⼀道就是利⽤这⼀思想的典型例题。题⽬⼤意是有把⼀块⽆限长的⽊板锯成⼏块给定长度的⼩⽊板，每次锯都需要⼀定费⽤，费⽤就是当前锯的⽊板的长度。给定各个要求的⼩⽊板的长度以及⼩⽊板的个数，求最⼩的费⽤。以要求3块长度分别为5,8,5的⽊板为例：先从⽆限长的⽊板上锯下长度为21的⽊板，花费21；再从长度为21的⽊板上锯下长度为5的⽊板，花费5；再从长度为16的⽊板上锯下长度为8的⽊板，花费8；总花费=21+5+8=34。利⽤Huffman思想，要使总费⽤最⼩，那么每次只选取最⼩长度的两块⽊板相加，再把这些和累加到总费⽤中即可。为了提⾼效率，使⽤优先队列优化，并且还要注意使⽤long long int保存结果。AC代码：#include#include#includeusing namespace std;int main(){ long long int sum; int i,n,t,a,b; while(~scanf("%d",&n)) { priority_queue,greater >ra算法

Dijkstra算法是由ra于1959年提出，是⽬前公认的最好的求解最短路径的⽅法，使⽤的条件是图中不能存在负边。算法解决的是单个源点到其他顶点的最短路径问题，其主要特点是每次迭代时选择的下⼀个顶点是标记点之外距离源点最近的顶点，简单的说就是bfs+贪⼼算法的思想。#include#include#define INF 1000#define MAX_V 100using namespace std; int main(){ int V,E; int i,j,m,n; int cost[MAX_V][MAX_V]; int d[MAX_V]; bool used[M10.最⼩⽣成树算法

设⼀个⽹络表⽰为⽆向连通带权图G =(V, E) , E中每条边(v,w)的权为c[v][w]。如果G的⼦图G’是⼀棵包含G的所有顶点的树，则称G’为G的⽣成树。⽣成树的代价是指⽣成树上各边权的总和，在G的所有⽣成树中，耗费最⼩的⽣成树称为G的最⼩⽣成树。例如在设计通信⽹络时，⽤图的顶点表⽰城市，⽤边(v,w)的权c[v][w]表⽰建⽴城市v和城市w之间的通信线路所需的费⽤，最⼩⽣成树给出建⽴通信⽹络的最经济⽅案。构造最⼩⽣成树的Kruskal算法和Prim算法都利⽤了MST(最⼩⽣成树)性质：设顶点集U是V的真⼦集(可以任意选取)，如果(u,v)∈E为横跨点集U和V—U的边，即u∈U，v∈V- U，并且在所有这样的边中，(u,v)的权c[u][v]最⼩，则⼀定存在G的⼀棵最⼩⽣成树，它以(u,v)为其中⼀条边。使⽤反证法可以很简单的证明此性质。假设对G的任意⼀个最⼩⽣成树T，针对点集U和V—U，(u,v)∈E为横跨这2个点集的最⼩权边，T不包含该最⼩权边，但T包括节点u和v。将添加到树T中，树T将变为含回路的⼦图，并且该回路上有⼀条不同于的边,u’∈U,v’∈V-U。将删去，得到另⼀个树T’，即树T’是通过将T中的边替换为得到的。由于这2条边的耗费满⾜c[u][v]≤c[u’][v’]，故即T’耗费≤T的耗费，这与T是任意最⼩⽣成树的假设相⽭盾，从⽽得证。Prim算法每⼀步都选择连接U和V-U的权值最⼩的边加⼊⽣成树。#include#include#define MAX_V 100#define INF 1000using namespace std; int main(){ int V,E; int i,j,m,n; int cost[MAX_V][MAX_V]; int mincost[MAX_V]; bool

Kruskal算法每⼀步直接将权值最⼩的不成环的边加⼊⽣成树，我们借助并查集这⼀数据结构可以完美实现它。#include#include#define MAX_E 100using namespace std; struct edge{ int u,v,cost; };int pre[MAX_E];edge es[MAX_E];int find(int x);void initvalue(int x);bool sa