贪心算法( 二 ) _生活百科

例题分析0-1背包问题有一个背包，背包容量是M=150kg 。有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问题，用贪心法并不一定可以求得最优解，以后了解了动态规划算法后本题就有了新的解法。马踏棋盘在8×8方格的棋盘上，从任意指定方格出发，为马寻找一条走遍棋盘每一格并且只经过一次的一条路径。【初步设计】首先这是一个搜寻问题，运用深度优先搜寻进行求解。算法如下：⒈ 输入初始位置坐标x,y； ⒉ 步骤 c:如果c> 64输出一个解，返回上一步骤c--（x,y) ← c计算(x,y）的八个方位的子结点，选出那些可行的子结点循环遍历所有可行子结点，步骤c++重複2显然⑵是一个递归调用的过程，大致如下：C++程式：#define N 8void dfs(int x,int y,int count){ int i,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;ProcedureFind(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.