学无止境。算法博大精深啊，一个贪心算法里面就隐含了这么多不同的场景实现，每个场景下的算法就有多种不同的实现，个人写法不一也成就了各种不同的漂亮算法，看了这些实现，也让我开拓了思维，这个世界的方案永远没有最完美的只有最合适的～ ！
1、贪心算法概念
贪心算法也叫贪婪算法，当然叫法随意。主要目的是在问题求解时，做出最正确的判断＝ ＝，这不是贪心是啥？在计算机工程领域当中，就是说不考虑整体最优算法而是从局部做到最优解。当然贪心是算法不能对所有的问题都能得到整体都最优解，但对多数个问题还是能得到近似乎最优解的方案。
2、贪心算法特性
2.1简略说明
建立数学模型来描述问题。
把求解的问题分成若干个子问题。
对每一子问题求解，得到子问题的局部最优解。
把子问题的解局部最优解合成原来解问题的一个解。
2.2详解特性
⑴ 有一个以最优方式来解决的问题。为了构造问题的解决方案，有一个候选的对象的集合：比如不同面值的硬币。
⑵ 随着算法的进行，将积累起其它两个集合：一个包含已经被考虑过并被选出的候选对象，另一个包含已经被考虑过但被丢弃的候选对象。
⑶ 有一个函数来检查一个候选对象的集合是否提供了问题的解答。该函数不考虑此时的解决方法是否最优。
⑷ 还有一个函数检查是否一个候选对象的集合是可行的，也即是否可能往该集合上添加更多的候选对象以获得一个解。和上一个函数一样，此时不考虑解决方法的最优性。
⑸ 选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解。
⑹ 最后，目标函数给出解的值。
为了解决问题，需要寻找一个构成解的候选对象集合，它可以优化目标函数，贪婪算法一步一步的进行。起初，算法选出的候选对象的集合为空。接下来的每一步中，根据选择函数，算法从剩余候选对象中选出最有希望构成解的对象。如果集合中加上该对象后不可行，那么该对象就被丢弃并不再考虑；否则就加到集合里。每一次都扩充集合，并检查该集合是否构成解。如果贪婪算法正确工作，那么找到的第一个解通常是最优的。
3、贪心算法实现过程
从问题的某一初始解出发；while 能朝给定总目标前进一步 do ,求出可行解的一个解元素；最后，由所有解元素组合成问题的一个可行解。
4、经典场景说明
4.1 好处
对于大部分的问题，贪心法通常都不能找出最佳解（不过也有例外），因为他们一般没有测试所有可能的解。贪心法容易过早做决定，因而没法达到最佳解。例如，所有对图着色问题已知的贪心法，和所有对NP完全问题的贪心法, 都无法确保得到最佳解。然而，贪心法的好处在于容易设计和很多时能达到好的近似解。
4.2 场景
（1）贪心法在系统故障诊断策略生成乃至高校的排课系统中都可使用案例详情参考 资料分享中得6和7
（2）背包问题：一个旅行者有一个最多能用m公斤的背包，现在有n种物品，每件的重量分别是W1，W2，...,Wn,每件的价值分别为C1,C2,...,Cn.若的每种物品的件数足够多,求旅行者能获得的最大总价值。参考资料分享5
（4）马踏棋盘：马的遍历问题。在8×8方格的棋盘上，从任意指定方格出发，为马寻找一条走遍棋盘每一格并且只经过一次的一条最短路径。（参考场景代码实现）
(5) 如把3／7和13/23分别化为三个单元分数的和等。
5、场景代码实现
其实所有场景代码都会有一堆漂亮的代码实现，这里我实现下马踏棋盘和一个数学计算的经典算法。其他算法实现在我的资料分享中里面已经包含在内～
5.1 马踏棋盘
5.1.1 问题描述
马的遍历问题。在8×8方格的棋盘上，从任意指定方格出发，为马寻找一条走遍棋盘每一格并且只经过一次的一条最短路径。
5.1.2 设计
首先这是一个搜索问题，运用“深度优先搜索”进行求解，这个深度有限搜索后续会给大家分享，这个搜索算法里面，又包含多种如知道的欢迎大家分享如不知道的请听下回分解。
算法大致顺序
（1）输入初始化的坐标x和y;
（2）假设当前的步骤为a；
（3）当a>64时输出一个解，返回上一步步骤a－－;
（4）计算（x,y）八个方向的子节点，选出可行的子结点；
（5）循环所有可行的子结点，步骤a++重复调用（这个地方包括了一个递归）；
5.1.3 代码实现
package study.arithmetic;
public class Horses {
//棋盘格数
int gridNum = 8;
//结果计算器
int count = 0;
//行
int[] line = new int[8];
//列
int[] column = new int[8];
int[][] results = new int[gridNum][gridNum];
public void HorsesAction(int x,int y,int count){
results[x][y] = count; //放置第z个棋子
if(count == gridNum*gridNum){
for(int i=0; i < gridNum; i++) {
for(int j=0; j < gridNum; j++){
System.out.println(results[i][j]);
}
}
count++; //结果计数
return;
}
for(int i=0; i
=0 && (y+column[i])>=0 //下一位置能否
&& (x+line[i])
首页 上一页 1 2 下一页 尾页 1/2/2