贪婪算法的应用实例

‘壹’ 贪心算法

#include <stdio.h>

#define M 100

void main()

{

int i,j,k,temp,m,n;

int t[M]={2,14,4,16,6,5,3},p[M]={1,2,3,4,5,6,7},s[M],d[M]={0};

m=3;n=7;

for(i=0;i<7;i++)

for(j=0;j<7-i;j++)

if(t[j]<t[j+1])

{

temp=t[j];

t[j]=t[j+1];

t[j+1]=temp;

temp=p[j];

p[j]=p[j+1];

p[j+1]=temp;

}

for(i=0;i<m;i++) //求时间。

{

s[i]=p[i];

d[i]=t[i];

}

for(k=0;k<m;k++)

printf(" %d",d[k]);

printf("\n");

for(i=m;i<n;i++)

{

for(k=0;k<m-1;k++) //求最小。

{

temp=d[k];

if(temp>d[k+1])

{temp=d[k+1];j=k+1;}

}

printf("这是最小下标的： %d\n",j);

printf("最小的值： %d\n",temp);

for(k=0;k<m;k++)

printf(" %d",d[k]);

printf("\n");

//j=temp;

s[j]=s[j]+p[i];

d[j]=d[j]+t[i];

}

printf("\n");

for(k=0;k<7;k++)

printf(" %d",t[k]);

printf("\n");

for(k=0;k<7;k++)

printf(" %d",p[k]);

printf("\n");

for(k=0;k<m;k++)

printf(" %d",s[k]);

printf("\n");

for(k=0;k<m;k++)

printf(" %d",d[k]);

printf("\n");

}

‘贰’ 贪心算法的例题分析

例题1、
[0-1背包问题]有一个背包，背包容量是M=150。有7个物品，物品不可以分割成任意大小。
要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。
物品 A B C D E F G
重量 35kg 30kg 6kg 50kg 40kg 10kg 25kg
价值 10$ 40$ 30$ 50$ 35$ 40$ 30$
分析：
目标函数：∑pi最大
约束条件是装入的物品总重量不超过背包容量：∑wi<=M(M=150）
⑴根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？
⑵每次挑选所占重量最小的物品装入是否能得到最优解？
⑶每次选取单位重量价值最大的物品，成为解本题的策略。
值得注意的是，贪心算法并不是完全不可以使用，贪心策略一旦经过证明成立后，它就是一种高效的算法。
贪心算法还是很常见的算法之一，这是由于它简单易行，构造贪心策略不是很困难。
可惜的是，它需要证明后才能真正运用到题目的算法中。
一般来说，贪心算法的证明围绕着：整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。
对于例题中的3种贪心策略，都是无法成立（无法被证明）的，解释如下：
⑴贪心策略：选取价值最大者。
反例：
W=30
物品：A B C
重量：28 12 12
价值：30 20 20
根据策略，首先选取物品A，接下来就无法再选取了，可是，选取B、C则更好。
⑵贪心策略：选取重量最小。它的反例与第一种策略的反例差不多。
⑶贪心策略：选取单位重量价值最大的物品。
反例：
W=30
物品：A B C
重量：28 20 10
价值：28 20 10
根据策略，三种物品单位重量价值一样，程序无法依据现有策略作出判断，如果选择A，则答案错误。
【注意：如果物品可以分割为任意大小，那么策略3可得最优解】
对于选取单位重量价值最大的物品这个策略，可以再加一条优化的规则：对于单位重量价值一样的，则优先选择重量小的！这样，上面的反例就解决了。
但是，如果题目是如下所示，这个策略就也不行了。
W=40
物品：A B C
重量：25 20 15
价值：25 20 15
附：本题是个DP问题，用贪心法并不一定可以求得最优解，以后了解了动态规划算法后本题就有了新的解法。
例题2、
马踏棋盘的贪心算法
123041-23 XX
【问题描述】
马的遍历问题。在8×8方格的棋盘上，从任意指定方格出发，为马寻找一条走遍棋盘每一格并且只经过一次的一条路径。
【初步设计】
首先这是一个搜索问题，运用深度优先搜索进行求解。算法如下：
⒈ 输入初始位置坐标x,y；
⒉ 步骤 c:
如果c> 64输出一个解，返回上一步骤c--
（x,y) ← c
计算(x,y）的八个方位的子结点，选出那些可行的子结点
循环遍历所有可行子结点，步骤c++重复2
显然⑵是一个递归调用的过程，大致如下：
C++程序： #defineN8voiddfs(intx,inty,intcount){inti,tx,ty;if(count>N*N){output_solution();//输出一个解return;}for(i=0;i<8;i++){tx=hn[i].x;//hn[]保存八个方位子结点ty=hn[i].y;s[tx][ty]=count;dfs(tx,ty,count+1);//递归调用s[tx][ty]=0;}}Pascal程序： ProgramYS;ConstFXx:array[1..8]of-2..2=（1,2,2,1,-1,-2,-2,-1）；FXy:array[1..8]of-2..2=（2,1,-1,-2,-2,-1,1,2）；VarRoad:array[1..10,1..10]ofinteger;x,y,x1,y1,total:integer;ProcereFind(x,y:integer);varNx,Ny,i:integer;BeginFori:=1to8dobegin{8个方向}If(x+FXx[i]in[1..8])and(y+FXy[i]in[1..8])Then{确定新坐标是否越界}IfRoad[x+Fxx[i],y+Fxy[i]]=0Thenbegin{判断是否走过}Nx:=x+FXx[i];Ny:=y+FXy[i];Road[Nx,Ny]:=1;{建立新坐标}If(Nx=x1）and(Ny=y1）Theninc(total)elseFind(Nx,Ny);{递归}Road[Nx,Ny]:=0{回朔}endendEnd;BEGIN{Main}Total:=0;FillChar(Road,sizeof(road),0);Readln(x,y);{读入开始坐标}Readln(x1,y1）；{读入结束坐标}If(x>10）or(y>10）or(x1>10）or(y1>10）Thenwriteln('Error'){判断是否越界}ElseFind(x,y);Writeln('Total:',total){打出总数}END.这样做是完全可行的，它输入的是全部解，但是马遍历当8×8时解是非常之多的，用天文数字形容也不为过，这样一来求解的过程就非常慢，并且出一个解也非常慢。
怎么才能快速地得到部分解呢？
【贪心算法】
其实马踏棋盘的问题很早就有人提出，且早在1823年，J.C.Warnsdorff就提出了一个有名的算法。在每个结点对其子结点进行选取时，优先选择‘出口’最小的进行搜索，‘出口’的意思是在这些子结点中它们的可行子结点的个数，也就是‘孙子’结点越少的越优先跳，为什么要这样选取，这是一种局部调整最优的做法，如果优先选择出口多的子结点，那出口少的子结点就会越来越多，很可能出现‘死’结点（顾名思义就是没有出口又没有跳过的结点），这样对下面的搜索纯粹是徒劳，这样会浪费很多无用的时间，反过来如果每次都优先选择出口少的结点跳，那出口少的结点就会越来越少，这样跳成功的机会就更大一些。这种算法称为为贪心算法，也叫贪婪算法或启发式算法，它对整个求解过程的局部做最优调整，它只适用于求较优解或者部分解，而不能求最优解。这样的调整方法叫贪心策略，至于什么问题需要什么样的贪心策略是不确定的，具体问题具体分析。实验可以证明马遍历问题在运用到了上面的贪心策略之后求解速率有非常明显的提高，如果只要求出一个解甚至不用回溯就可以完成，因为在这个算法提出的时候世界上还没有计算机，这种方法完全可以用手工求出解来，其效率可想而知。

‘叁’ 收集各类贪心算法（C语言编程）经典题目

举个例子,假如你买东西，老板需要找给你99分钱，他有上面面值分别为25分，10分，5分，1分的硬币（都是假如，不符合实际），他得找你3个25分，2个10分的，4个1分的才为最佳方案！
用贪心算法编写程序实现！
main()
{
int
i,a[5],b[4],c[4];
/*
define
the
type
of
the
money*/
a[1]=25;
a[2]=10;
a[3]=5;
a[4]=1;
printf("please
input
you
money
(fen):\n");
scanf("%d",&b[0]);
for
(i=1;i<=4;i++)
{
b[i]=b[i-1]%a[i];
/*take
n
25
off
and
money
left*/
c[i]=(b[i-1]-b[i])/a[i];
/*
n
*/
printf("%d
is
%d\n",a[i],c[i]);
}
getch();
}

‘肆’ 5.贪心算法的核心思想。6.什么是递归什么是迭代两者的区别，举例说明。7.回溯的含义是什么举例

1、贪心算法主要是把问题分成很多局部问题，用局部最优解合成整体最优解。因此使用这种算法需要此问题满足两个条件，一个是能够分成多个能够求解的局部问题，第二个就是局部问题的解能够合成最优解。和动态规划、回溯等相比差别就是再不回溯的前提下找出整体最优解或者接近最优解，速度快但应用有比较大的限制。

2、迭代也叫递推，通过重复执行某一步骤或者函数来求得计算结果
递归是指函数中直接或者间接调用自身
举例：
求a乘以2的10次方等于几
迭代：
for (i=0;i<10;i++)
a *= 2;

递归：
int db(int a,int num)
{
if (num<10)
return 2 * db(a,num+1);
else
return 1;
}

db(a,0);

3、回溯的含义就是在搜索问题的状态过程中，如果不能继续前进，再向后回到岔口，换一条路继续搜索，直到搜索完所有状态或者查找到需要的状态。
举例：（最典型的就是树的深度搜索，下面举一个简单的例子）
int a[10]={5,3,7,9,3,2,5,6,9,1};//从3开始查找1
int read[10]=(0);//是否查找过
int readNum = 0;//查找过的个数
int forward = 1;//1为左，2为右
int tmp = 0,index = 5;

tmp = a[index];
read[index] = 1;
readNum++;
while (tmp != 1 || readNum != 10)
{
if (forward == 1)
index --;
else
index++;
if (!read[index])
{
tmp = a[index];
read[index] = 1;
readNum++;
}

if (index <=0 || index>=9)
forward = 3 - forward;
}

‘伍’ 适度贪婪的成功事例

算法中的贪婪算法，很着名的一个例子是使用贪婪算法解马踏棋盘

‘陆’ 什么是贪心算法，用实例分析贪心算法是如何解决实际问题

比如： int a=3,b=4,c; c=a+++b; 将被解释为 c=(a++)+b; 而不会被解释为 c=a+(++b); 贪心算法的主要意义是从左至右依次解释最多的符号！

‘柒’ 贪心算法的数学应用

如把3/7和13/23分别化为三个单位分数的和
【贪心算法】
设a、b为互质正整数，a<b 分数a/b 可用以下的步骤分解成若干个单位分数之和：
步骤一： 用b 除以a，得商数q1 及余数r1。（r1=b - a*q1）
步骤二：把a/b 记作：a/b=1/(q1+1）+(a-r1)/b(q1+1）
步骤三：重复步骤2，直到分解完毕
3/7=1/3+2/21=1/3+1/11+1/231
13/23=1/2+3/46=1/2+1/16+1/368
以上其实是数学家斐波那契提出的一种求解埃及分数的贪心算法，准确的算法表述应该是这样的：
设某个真分数的分子为a，分母为b;
把b除以a的商部分加1后的值作为埃及分数的某一个分母c；
将a乘以c再减去b，作为新的a；
将b乘以c，得到新的b；
如果a大于1且能整除b，则最后一个分母为b/a；算法结束；
或者，如果a等于1，则，最后一个分母为b；算法结束；
否则重复上面的步骤。
备注：事实上，后面判断a是否大于1和a是否等于1的两个判断可以合在一起，及判断b%a是否等于0，最后一个分母为b/a，显然是正确的。
PHP代码： classtanxin{public$weight;public$price;publicfunction__construct($weight=0,$price=0){$this->weight=$weight;$this->price=$price;}}//生成数据$n=10;for($i=1;$i<=$n;$i++){$weight=rand(1,20);$price=rand(1,10);$x[$i]=newtanxin($weight,$price);}//输出结果functiondisplay($x){$len=count($x);foreach($xas$val){echo$val->weight,'',$val->price;echo'<br>';}}//按照价格和重量比排序functiontsort(&$x){$len=count($x);for($i=1;$i<=$len;$i++){for($j=1;$j<=$len-$i;$j++){$temp=$x[$j];$res=$x[$j+1]->price/$x[$j+1]->weight;$temres=$temp->price/$temp->weight;if($res>$temres){$x[$j]=$x[$j+1];$x[$j+1]=$temp;}}}}//贪心算法functiontanxin($x,$totalweight=50){$len=count($x);$allprice=0;for($i=1;$i<=$len;$i++){if($x[$i]->weight>$totalweight)break;else{$allprice+=$x[$i]->price;$totalweight=$totalweight-$x[$i]->weight;}}if($i<$len)$allprice+=$x[$i]->price*($totalweight/$x[$i]->weight);return$allprice;}tsort($x);//按非递增次序排序display($x);//显示echo'0-1背包最优解为:';echotanxin($x);java源代码 packagemain;importjava.util.ArrayList;importjava.util.Collections;importjava.util.Comparator;importjava.util.List;importjava.util.Random;publicclassMain{/***测试*/publicstaticvoidmain(String[]args){//1.随机构造一批任务List<Pair<Integer>>inputList=newArrayList<Pair<Integer>>();Randomrand=newRandom();for(intn=0;n<20;++n){Integerleft=rand.nextInt(100);Integerright=left+rand.nextInt(100)+1;Pair<Integer>pair=newPair<Integer>(left,right);inputList.add(pair);}//将任务列表按结束时间排序（也就是根据right字段进行排序）sortByRight(inputList);printPairList(inputList);//执行算法List<Pair<Integer>>outputList=algorithm(inputList);System.out.println();printPairList(outputList);}/***贪心算法**@paraminputList*@return使数量最多的任务方案*/publicstatic<TextendsComparable<T>>List<Pair<T>>algorithm(List<Pair<T>>inputList){if(null==inputList||inputList.size()==0||inputList.size()==1){returninputList;}sortByRight(inputList);List<Pair<T>>outputList=newArrayList<Pair<T>>();intlast=0;outputList.add(inputList.get(last));intintputSize=inputList.size();for(intm=1;m<intputSize;++m){Pair<T>nextPair=inputList.get(m);TnextLeft=nextPair.getLeft();Pair<T>lastOutPair=inputList.get(last);TlastRight=lastOutPair.getRight();intflag=nextLeft.compareTo(lastRight);if(flag>=0){outputList.add(nextPair);last=m;}}returnoutputList;}/***对传入的List<Pair<T>>对象进行排序，使Pair根据right从小到大排序。**@paraminputList*/privatestatic<TextendsComparable<T>>voidsortByRight(List<Pair<T>>inputList){CompareByRight<T>comparator=newCompareByRight<T>();Collections.sort(inputList,comparator);}/***打印一个List<Pair<T>>对象。**@paraminputList*/privatestatic<TextendsComparable<T>>voidprintPairList(List<Pair<T>>inputList){for(Pair<T>pair:inputList){System.out.println(pair.toString());}}}/***根据Pair.right比较两个Pair。用于Conlections.sort()方法。**@param<T>*/classCompareByRight<TextendsComparable<T>>implementsComparator<Pair<T>>{/*@Override*/publicintcompare(Pair<T>o1,Pair<T>o2){Tr1=o1.getRight();Tr2=o2.getRight();intflag=r1.compareTo(r2);returnflag;}}/***代表一个任务对象。有点装逼用模板来写了。left表示开始时间，right表示结束时间。**@param<T>*/classPair<TextendsComparable<T>>{privateTleft;privateTright;publicPair(Tleft,Tright){this.left=left;this.right=right;}@OverridepublicStringtoString(){return[left=+left.toString()+','+right=+right.toString()+']';}publicTgetLeft(){returnleft;}publicvoidsetLeft(Tleft){this.left=left;}publicTgetRight(){returnright;}publicvoidsetRight(Tright){this.right=right;}}

‘捌’ 怎样应用贪心算法求得最优解

动态规划要求。。具有最优子结构，记f[i]最优时，f[i - 1]的解也最优。。。最终可以得到最优解

贪心算法，一般只能得到近优解或者局部最优解。。

‘玖’ 求背包问题贪心算法实例结果

找零钱问题：以人民币1元，2元，5元，10元，20元，50元，100元为例，要求所找的张数最少
背包问题：假设物体重量W1，W2．．．Wn其对应的价值为P1，P2．．．Pn，物体可分割，求装入重量限制为m的背包中的物体价值最大．可用P/W来解答．
#include<iostream>
#include<algorithm>
using namespace std;
struct good//表示物品的结构体
{
double p;//价值
double w;//重量
double r;//价值与重量的比
}a[2000];
double s,value,m;
int i,n;
bool bigger(good a,good b)
{
return a.r>b.r;
}
int main()
{
scanf("%d",&n);//物品个数
for (i=0;i<n;i++)
{
scanf("%lf%lf",&a[i].w,&a[i].p);
a[i].r=a[i].p/a[i].w;
}
sort(a,a+n,bigger);//调用sort排序函数，你大概不介意吧，按照价值与重量比排序贪心
scanf("%lf",&m);//读入包的容量m
s=0;//包内现存货品的重量
value=0;//包内现存货品总价值
for (i=0;i<n&&s+a[i].w<=m;i++)
{
value+=a[i].p;
s+=a[i].w;
}
printf("The total value in the bag is %.2lf.\n",value);//输出结果
return 0;
}

‘拾’ 哪些常见算法属于贪婪算法

显然KMP和FLOYD算法不是贪心算法，FLOYD算法是使用了类似于动态规划的思想，而KMP算法则是对串的前缀进行去处理得到所有可能出现匹配的位置从而减少不必要的位移。贪心算法可能还有很多，但是一般能用到的可能只有这些。在确定一个问题是否能用贪心来解决的时候应该线能够证明在这里使用贪心算法的正确性（详见算法导论）