贪心算法pascal贪心算法是什么啊?

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

动态规划要求。

。

具有最优子结构，记f[i]最优时，f[i - 1]的解也最优。

。

。

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

。

关于编程的贪心法

定义 所谓贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。

也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。

贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。

[编辑本段]贪心算法的基本思路 1.建立数学模型来描述问题。

2.把求解的问题分成若干个子问题。

3.对每一子问题求解，得到子问题的局部最优解。

4.把子问题的解局部最优解合成原来解问题的一个解。

实现该算法的过程： 从问题的某一初始解出发； 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) （1）根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？ （2）每次挑选所占重量最小的物品装入是否能得到最优解？ （3）每次选取单位重量价值最大的物品，成为解本题的策略。

值得注意的是，贪心算法并不是完全不可以使用，贪心策略一旦经过证明成立后，它就是一种高效的算法。

贪心算法还是很常见的算法之一，这是由于它简单易行，构造贪心策略不是很困难。

可惜的是，它需要证明后才能真正运用到题目的算法中。

一般来说，贪心算法的证明围绕着：整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。

对于例题中的3种贪心策略，都是无法成立（无法被证明）的，解释如下： （1）贪心策略：选取价值最大者。

反例： W=30 物品：A B C 重量：28 12 12 价值：30 20 20 根据策略，首先选取物品A，接下来就无法再选取了，可是，选取B、C则更好。

（2）贪心策略：选取重量最小。

它的反例与第一种策略的反例差不多。

（3）贪心策略：选取单位重量价值最大的物品。

反例： W=30 物品：A B C 重量：28 20 10 价值：28 20 10 根据策略，三种物品单位重量价值一样，程序无法依据现有策略作出判断，如果选择A，则答案错误。

【注意：如果物品可以分割为任意大小，那么策略3可得最优解】 对于选取单位重量价值最大的物品这个策略，可以再加一条优化的规则：对于单位重量价值一样的，则优先选择重量小的！这样，上面的反例就解决了。

但是，如果题目是如下所示，这个策略就也不行了。

W=40 物品：A B C 重量：28 20 15 价值：28 20 15 附：本题是个NP问题，用贪心法并不一定可以求得最优解，以后了解了动态规划算法后本题就有了新的解法。

[编辑本段]备注 贪心算法当然也有正确的时候。

求最小生成树的Prim算法和Kruskal算法都是漂亮的贪心算法。

所以需要说明的是，贪心算法可以与随机化算法一起使用，具体的例子就不再多举了。

（因为这一类算法普及性不高，而且技术含量是非常高的，需要通过一些反例确定随机的对象是什么，随机程度如何，但也是不能保证完全正确，只能是极大的几率正确） [编辑本段]附贪心算法成功案例之一 马踏棋盘的贪心算法 123041-23 XX 【问题描述】 马的遍历问题。

在8×8方格的棋盘上，从任意指定方格出发，为马寻找一条走遍棋盘每一格并且只经过一次的一条最短路径。

【初步设计】 首先这是一个搜索问题，运用深度优先搜索进行求解。

算法如下： 1、 输入初始位置坐标x,y； 2、 步骤 c: 如果c> 64输出一个解，返回上一步骤c-- (x,y) ← c 计算(x,y)的八个方位的子结点，选出那此可行的子结点 循环遍历所有可行子结点，步骤c++重复2 显然（2）是一个递归调用的过程，大致如下： void dfs(int x,int y,int count) { int i,tx,ty; if(count> N*N) { output_solution();//输入一个解 return; }

pascal贪心算法是什么啊?

贪心算法 1．概念 贪心算法是从问题的某一个初始解出发逐步逼近给定的目标，以 尽可能快地求得更好的解。

当达到某算法中的某一步不能再继续 前进时，算法停止。

这时就得到了问题的一个解，但不能保证求 得的最后解是最优的。

在改进算法中，贪心算法演化为爬山法。

2．特点及使用范围 贪心算法的优点在于时间复杂度极底。

贪心算法与其他最优化算 法的区别在于：它具有不可后撤性，可以有后效性，一般情况下 不满足最优化原理。

贪心算法的特点就决定了它的适用范围，他 一般不适用于解决可行性问题，仅适用于较容易得到可行解的最 优性问题。

这里较容易得到可行解的概念是：当前的策略选择后， 不会或极少使后面出现无解的情况。

另外，对于近年来出现的交 互性题目，贪心算法是一个较好的选择。

这是因为，在题目中， 一个策略的结果是随题目的进行而逐渐给出的，我们无法预先知 道所选策略的结果，这与贪心算法不考虑策略的结果和其具有后 效性的特点是不谋而合的。

当然，贪心算法还可以为搜索算法提 供较优的初始界值。