这类过程优化问题的新方法Р———动态规划[6]。Р第二节 0-1背包问题描述Р0-1背包问题:给定一个背包和n件物品。物品i的重量为wi,其价值为vi,背包的总容量为C。问应该如何选择装入背包中物品的总价值最大?Р问题约定:在选择装人背包的物品时.对每种物品i只有两种选择:即装人或不装人背包。不能将物品 i装入背包多次.也不能只装人部分的物品 i。在以下各种方法的描述中,设xi表示物品i装入背包的情况,则当xi=0时,表示物品i没有被装入背包,反之,当xi=1时,表示物品i被装入背包。Р此问题的形式化描述是,给定C > 0,wi> 0,1≤i ≤n,要求找出一个n元向量(x1,x2,…,xn), xi∈{0,1},1≤i≤n,使得Р即此问题的约束条件和目标函数:Р 第二章 0-1背包问题经典算法分析Р 第一节贪心算法Р(一)贪心算法思想[7]:贪心算法往往不是从整体加以考虑,而只是从局部方面出发,获得一个局部最优解,使用贪心算法找出最优量度标准至关重要,这一量度的寻找一般通过经验和推测形成一种量度标准,通过实践检测来测试规律。以当前的情况标准作为基础,做出最优的选择一般能够迅速地找到最优解不必耗费大量的时间来搜寻最优解。根据找到的最优量标准,每一步进行最优选择,获得一个最优解,这种算法让人感觉到每一步选择都是最佳的,这种标准应用于整个选择过程,不能发生标准的更换。现在使用这一思想解决0-1背包问题的标准有三个:Р1)收益优先的标准,就是首先根据价值vi的大小,从大到小排列顺序,再逐一放到背包中。直到所放物品的重量达到背包所允许的最大重量。Р2)重量优先的标准,按照重量的先后顺序放到背包中,忽视收益对背包的影响,装到背包所能允许的最大重量为止。Р3)以vi/wi的大小作为选择的标准,按照该标准从大到小的顺序排列,再按照此顺序将物品放入到背包中,直到背包所能允许的最大重量为止。
全文预览
