算法设计与分析ppt课件.pptxVIP

;;算法设计与分析贪心算法;在安排时应该将结束时间早的活动尽量往前安排，好给后面的活动安排留出更多的空间，从而达到安排最多活动的目标。

贪心准则应当是：在未安排的活动中挑选结束时间最早的活动安排。;算法设计与分析贪心算法;算法设计与分析贪心算法;2.最优子结构性质

当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。

问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。;3.贪心算法与动态规划算法的差异 ;算法设计与分析贪心算法;于是，背包问题归结为寻找一个满足约束条件，并使目标函数达到最大的解向量X=(x1,x2,…,xn)。;每次捡最轻的物品装；

每次捡价值最大的装；

每次装包时既考虑物品的重量又考虑物品的价值，也就是说每次捡单位价值最大的装。;首先计算每种物品单???重量的价值vi/wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。

若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。

依此策略处理，直到背包装满为止。;;0-1背包问题：

给定n种物品和一个背包。物品i的重量是wi，其价值为vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?

;算法设计与分析贪心算法;算法设计与分析贪心算法;1.算法描述

最优装载问题可用贪心算法求解。采用重量最轻者先装的贪心选择策略，可产生最优装载问题的最优解。;算法设计与分析贪心算法;物品重量分别为15，10，27，18，船载重为50

定义：w[]={15,10,27,18}物品重量

T[]={1,0,3,2}物品从轻到重排序后序号

C=50船载重

贪心算法计算步骤：

w[T[0]]=10c,c=c-10=40

w[T[1]]=15c,c=c-15=25

w[T[2]]=18c,c=c-18=7

w[T[3]]=27c

;;设[x1,...,xn]是最优装载问题的一个满足贪心选择性质的最优解，则x1=1时,[x2,...,xn]是轮船载重量为c-w1且待装集装箱为{2,...,n}时相应最优装载问题的一个最优解。;算法设计与分析贪心算法;算法设计与分析贪心算法;[贪心近似算法]

采用最长处理时间作业优先的贪心策略.

当n≤m时,只要将机器i的[0,ti]时间区间分配给作业i即可;

当nm时,将n个作业依其所需的处理时间从大到小排序，然后依次将作业分配给空闲的处理机。;算法设计与分析贪心算法;;算法设计与分析贪心算法