(25/18,24/15,15/10=(1.389,16,1.5)。首先考虑单位价值大的物品装 包,即将物品2装包,此时获得效益值24,背包的剩余容量是5。然 后考虑装物品3,由于物品3的重量超出背包的剩余容量,只能装入 该物品5/15=1/2,至此背包已经装满,所得的总的效益值为 24+15/2=315。比前面的装法的效益值大。实践证明,选择能产生最 优解的贪心准则是设计贪心算法的核心问题。以下给出贪心算法流程 的伪代码。 贪心算法抽象化控制流程 Greedy(A,n)∥A[1n]代表那个输入 solution={};∥解向量初始化为空集 fori from l to n do xSelect(A); if Feasible(solution, x)then solution=Union(solution, x); endif endfor return( solution) end greedy 这里 Selecte(A)是按照谈心准则选取A种的输入项; Feasible( solution, x)是判断已知的解的部分 solution与新选取的x的结合 Union( solution, x)是否是可行解。过程〔redy描述了用贪心策略设计算法的主要工 作和基本控制流程。一旦给出一个特定的问题,就可将 Select, Feasible(25/18, 24/15, 15/10)=(1.389, 1.6, 1.5)。首先考虑单位价值大的物品装 包，即将物品 2 装包，此时获得效益值 24，背包的剩余容量是 5。然 后考虑装物品 3，由于物品 3 的重量超出背包的剩余容量，只能装入 该物品 5/15=1/2, 至此背包已经装满，所得的总的效益值为 24+15/2=31.5。比前面的装法的效益值大。实践证明，选择能产生最 优解的贪心准则是设计贪心算法的核心问题。以下给出贪心算法流程 的伪代码。 贪心算法抽象化控制流程 Greedy(A, n) // A[1:n]代表那个输入 solution={}; //解向量初始化为空集 for i from 1 to n do x=Select(A); if Feasible(solution, x) then solution=Union(solution, x); endif endfor return(solution); end Greedy 这里 Select(A)是按照谈心准则选取 A 种的输入项； Feasible(solution, x)是判断已知的解的部分solution与新选取的x的结合Union(solution, x)是否是可行解。过程 Greedy 描述了用贪心策略设计算法的主要工 作和基本控制流程。一旦给出一个特定的问题，就可将 Select，Feasible