null贪心算法(一)贪心算法(一)重庆教育学院
杨华千贪心算法的基本思想：贪心算法的基本思想：贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。几个概念：几个概念：(1) 约束条件：求解过程中必须满足的条件
(2) 可行解：满足约束条件的子集
(3) 目标函数：衡量可行解优劣的函数
(4) 最优解：使得目标函数取得极值的可行解贪心算法的基本要素：贪心算法的基本要素：(1) 贪心选择性质
贪心选择性质是指，所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。
(2) 最优子结构性质
当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。
背包问题－问题描述：背包问题－问题描述：给定n种物品和一个背包。物品i的重量是wi，其价值为pi，背包的容量为M。应如何选择装入背包的物品，使得装入背包中物品的总价值最大？在选择物品i装入背包时，可以选择物品i的一部分xi，而不一定要全部装入背包。背包问题－约束条件：背包问题－约束条件：极大化
约束条件
背包问题－基本步骤：背包问题－基本步骤：(1) 首先计算每种物品单位重量的价值pi/wi，
(2) 然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过M，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。背包问题－算法描述：背包问题－算法描述：void Knapsack(int n,float M,float p[],float w[],float x[])
{
Sort(n,v,w);
int i;
for (i=1;i<=n;i++) x[i]=0;
float c=M;
for (i=1;i<=n;i++) {
if (w[i]>c) break;
x[i]=1;
c-=w[i];
}
if (i<=n) x[i]=c/w[i];
}删数问题－问题描述：删数问题－问题描述：键盘输入一个高精度的正整数N，去掉其中任意S个数字后剩下的数字按原左右次序组成一个新的正整数。寻找一种
方案
气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载
使得剩下的数字组成的新数最小。删数问题－贪心要素：删数问题－贪心要素：以字符串形式输入N，使用尽可能逼近目标的贪心法来逐一删去其中S个数符，每一步总是选择一个剩下的数最小的数符删去。之所以作出这样贪心的选择，是因为删S个数符的全局最优解，包含了删一个数符的子问题的最优解。删数问题－基本步骤：删数问题－基本步骤：为保证删一个数符后的数最小，按高位→低位的方向搜索递减区间。若不存在递减区间，则删尾数符；否则删递减区间的首字符，这样形成了一个新数串。然后回到串首，重复上述规则，删下一个数符……依次类推，直至删除S个数符为止。删数问题－示例演示：删数问题－示例演示：N=‘178543’, S=4
1 7 8 5 4 3
1 7 5 4 3
1 5 4 3
1 4 3
1 3带期限的作业排序－问题描述：带期限的作业排序－问题描述：假定只能在一台机器上处理n个作业，每个作业均可在单位时间内完成；又假定每个作业i都有一个截止期限di>0，当且仅当作业i在它的期限截止以前完成被完成时，方可获得pj>0的效益。带期限的作业排序－可行解判断：带期限的作业排序－可行解判断：设J是k个作业的集合，δ=i1i2…ik是J中作业的一种排列，它使得di1≤ di2 ≤… dik。J是一个可行解，当且仅当J中的作业可以按照δ的次序而又不违反任何一个期限的情况来处理。
浙公网安备 33021202002483