数学模型-贪心算法及实例.pptVIP

数学建模竞赛中十类常用算法;

3.线性规划、整数规划、多元规划、二次规划等规划类算法。建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lingo软件求解。

4.图论算法。这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决。

5.动态规划、回溯有哪些信誉好的足球投注网站、分治算法、分支定界等计算机算法。这些算法是算法设计中比较常用的方法，

竞赛中很多场合会用到。;6.最优化理论的三大非经典算法：模拟退火算法、神经网络算法、遗传算法。这些问题是用来解决一

些较困难的最优化问题的，对于有些问题非常有帮助，但是算法的实现比较困难，需慎重使用。

7.网格算法和穷举法。两者都是暴力有哪些信誉好的足球投注网站最优点的算法，在很多竞赛题中有应用，当重点讨论模型本

身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具。

8.一些连续数据离散化方法。很多问题都是实际来的，数据可以是连续的，而计算机只能处理离散的

数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的。;9.数值分析算法。如果在比赛中采用高级语言进行编程的话，那些数值分析中常用的算法比方方程组

求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用。

10.图象处理算法。赛题中有一类问题与图形有关，即使问题与图形无关，论文中也会需要图片来说明

问题，这些图形如何展示以及如何处理就是需要解决的问题，通常使用MATLAB进行处理。;贪心算法;有下面几种面值的硬币：一元、五角、一角、五分、一分，假设要付给顾客2.89元的零钱，要求用最少的硬币。; 顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最??结果却是最优解的很好近似。;主要知识点：

活动安排问题

背包问题

最优装载

单源最短路径

最小生成树

;活动安排问题

;活动安排问题;活动安排问题;活动安排问题;活动安排问题;给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?〔假定物品可以分割成更小局部，亦即物品可以局部装入〕;例：;这个问题有三种看似合理的选择：;用贪心算法解背包问题的根本步骤：

首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。假设将这种物品全部装入背包后，背包内的物品总重量未超过C，那么选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。

具体算法可描述如下页：;floatknapsack(floatc,floatw[],floatv[],floatx[])

{

intn=v.length;

for(inti=0;in;i++)d[i]=(w[i],v[i],i);

MergeSort.mergeSort(d);

inti;

floatopt=0;

for(i=0;in;i++)x[i]=0;

for(i=0;in;i++){

if(d[i].wc)break;

x[d[i].i]=1;

opt+=d[i].v;

c-=d[i].w;

}

if(in){

x[d[i].i]=c/d[i].w;

opt+=x[d[i].i]*d[i].v;

}

returnopt;

};最优装载;floatloading(floatc,float[]w,int[]x)

{

intn=w.length;

for(inti=0;in;i++)

d[i]=(w[i],i);

MergeSort.mergeSort(d);

floatopt=0;

for(inti=0;in;i++)x[i]=0;

for(inti=0;ind[i].w=c;i++){

x[