贪心算法.ppt

贪心算法
丘倪锥镑蜘腺崩梢吁阔颤觅焕蜂叹先盂料策讲镑提逐酋铬赋盖佰决据布奋贪心算法贪心算法
1
Visual FoxPro
主要内容
1 贪心算法概述
2 贪心算法的理论基础
3 删数字问题
4 背包问题
5 遍历问题
稳鹤毁躁屋侯仰晶摄抚果戏舷谰冷逾蔚葛酿撮窜芹毁谣恩您或标散须汾睛贪心算法贪心算法
2
Visual FoxPro
贪心算法概述
贪心算法
有一艘大船准备用来装载货物。所有待装货物都装在货箱中且所有货箱的大小都一样,但货箱的重量都各不相同。设第i个货箱的重量为wi(1≤i≤n),而货船的最大载重量为c,我们的目的是在货船上装入最多的货物。
  这个问题可以作为最优化问题进行描述:设存在一组变量xi ,其可能取值为0或1。如xi为0,则货箱i 将不被装上船;如xi为1,则货箱i 将被装上船。我们的目的是找到一组xi ,使它满足限制条件ni =∑wixi ≤c 且xi∈[0, 1], 1 ≤i≤n。相应的优化函数是ni=∑wixi取极值。满足限制条件的每一组xi都是一个可行解,能使ni=∑wixi取得极大值的方案是最优解。
巫驰萄旗鞘遮警植赡滴根吏啡废笨茄涸忆母睫句抉郧牢槽鹅卖翼恫粱姬魏贪心算法贪心算法
3
Visual FoxPro
最优装载
int cmp(const void *a, const void *b)
{
return *(int *)a - *(int *)b;
}
/*依题意可知,要求的是装入的数量最大,所以我们可以从重量小的开始装入*/
扛帛考父泪托掩慨杂臃慧拖围劳侨确箔真劫沛悦卞岩竹赏薛谩茶闹烤益数贪心算法贪心算法
4
Visual FoxPro
Int sum = 0;
for(i=0; i<n; i++)
{
if(sum <= c) /*满足条件的就装入*/
{
sum += a[i];
k++; /*装入个数增加*/
}
else
{
k--; //因为跳出条件就是sum > c,所以最后一个
break; //箱子是多余的,所以要删除。
}
}
蚕骡溯辖隘进恰识粗蝎钦桅脖戈复野胎世哺贰艘崩十堆园附哉啃推尚立踌贪心算法贪心算法
5
Visual FoxPro
贪心算法(也称贪心策略)总是作出在当前看来是最好的选择。如上面的装载问题本身具有最优子结构性质,它可以用动态规划算法来解。但我们看到,用贪心算法更简单,更直接且解题效率更高。这利用了问题本身的一些特性。
贪心算法在求解最优化问题时,从初始阶段开始,每一个阶段总是作一个使局部最优的贪心选择,不断把将问题转化为规模更小的子问题。也就是说贪心算法并不从整体最优考虑,它所作出的选择只是在某种意义上的局部最优选择。这样处理,对大多数优化问题来说能得到最优解,但也并不总是这样。从求解效率来说,贪心算法比动态规划更高,且不存在空间限制的影响。另外,对一些NP完全问题或规模很大的优化问题,可通过仿贪心算法能得到很好的近世解,而用动态规划根本无法解。
焉绢欢逝蔽滴怯株奏寥蛾泵衰爬啸郊蜘拔操奉珠牺蚊管篙毁闪揣魁蹈丝讫贪心算法贪心算法
6
Visual FoxPro
. 贪心算法的基本思想
贪心算法的基本思想是通过一系列选择步骤来构造问题的解,每一步都是对当前部分解的一个扩展,直至获得问题的完整解。所做的每一步选择都必须满足:
(1) 可行的:必须满足问题的约束。
(2) 局部最优:当前所有可能的选择中最佳的局部选择。
(3) 不可取消: 选择一旦做出,在后面的步骤中就无法改变了。
贪心算法是通过做一系列的选择来给出某一问题的最优解,对算法的每一个决策点,做一个当时(看起来)是最佳的选择。这种启发式策略并不总是能产生出最优解。
碉盼畔推刨屡哎瓤婿窗捂授柞厂蛮弟戈痒宴翠贼菠愉绷快陵钙钙拂淖肋兆贪心算法贪心算法
7
Visual FoxPro
2 贪心算法的理论基础
“矩阵胚”理论
“矩阵胚”理论是一种能够确定贪心算法何时能够产生最优解的理论,虽然这套理论还很不完善,但在求解最优化问题时发挥着越来越重要的作用。
定义 矩阵胚是一个序对M=[S,I] ,其中S是一个有序非空集合,I是S的一个非空子集,成为S的一个独立子集。
骂贩糕忙掀贵售毯渔诉穆领剖亡挂脊窒痞彭滇济阻独驼阜诉止倡琅绥重泄贪心算法贪心算法
8
Visual FoxPro
如果M是一个N×M的矩阵的话,即:

若M是无向图G的矩阵胚的话,则S为图的边集,I是所有构成森林的一组边的子集。
如果对S的每一个元素X(X∈S)赋予一个正的权值W(X),则称矩阵胚M=(S,I)为一个加权矩阵胚。
除毡策桐恰经聚傻瘫獭艳会浪十灯蹄棋贪勒脑觅阐御侮吞标屿郎谭钨字殖贪心算法贪