贪心算法在背包中的应用

贪心算法在背包中的应用贪心算法在背包中的应用 实现这个算法是学习算法分析与设计这门课程的需要 贪心算法是所接触到的第一类算法 算法从局部的最优出发 简单而快捷 对于一个问题的最 优解只能用穷举法得到时 用贪心法是寻找问题次优解的较好算法 贪心法是一种改进了的分级处理方法 用贪心法设计算法的特点是一步一步地进行 根据某个 优化测度 可能是目标函数 也可能不是目标函数 每一步上都要保证能获得局部最优解 每一 步只考虑一个数据 它的选取应满足局部优化条件 若下一个数据与部分最优解连在一起不再是可 行解时 就不把该数据添加到部分解中 直到把所有数据枚举完 或者不能再添加为止 这种能够 得到某种度量意义下的最优解的分级处理方法称为贪心法 选择能产生问题最优解的最优度量标准是使用贪心法的核心问题 假定有 n 个物体和一个背包 物体 i 有质量 wi 价值为 pi 而背包的载荷能力为 M 若将物体 i 的 一部分 xi 1 i n 0 xi 1 装入背包中 则有价值 pi xi 在约束条件 w1 x1 w2 x2 wn xn M 下使目标 p1 x1 p2 x2 pn xn 达到极大 此处 0 xi0 1 i n 这个问题称为背包问题 Knapsack problem 要想得到最优解 就要在效益增长和背包容量消耗两者之间寻找平衡 也就是说 总应该把那 些单位效益最高的物体先放入背包 在实现算法的程序中 实现算法的核心程序倒没碰到很大的问题 然而实现寻找最优度量标准 程序时麻烦不断 在寻找最优度量标准时 大致方向是用冒泡排序算法 也就是根据 p i w i 的大小来对 w i 来 排序 在直接用此算法时 可以有如下的一段代码 根据效益 tempArray i 对重量 w i 排序 为进入贪心算法作准备 1 void sort float tempArray flaot w int n 2 int i 0 j 0 4 int index 0 用类似冒泡排序算法 根据效益 p i w i 对 w i 排序 7 for i 0 i n i 8 float swapMemory 0 10 float temp 1112 temp tempArray i 13 index i for j i 1 j n j 16 if temp tempArray j 18 temp tempArray j index j 对 w i 排序 25 swapMemory w index 26 w index w i w i swapMemory return 然而仔细对算法分析后可以发现 拿来主义 在这里用不上了 对算法的测试用例是 p 3 25 24 15 w 3 18 15 10 得到的结果如下 please input the total count of object 3 Please input array of p 25 24 15 Now please input array of w 18 15 10 sortResult i is 1 107374176 000000 1 1 600000 2 1 600000 after arithmetic data x i 0 000000 0 333333 0 000000 可以看到其效益为 x 3 1 4 1 6 1 5 于是在 M 20 的情况下 其预想中的输出结果是 0 1 0 5 然而事实上是不是就这样呢 当程序进入此函数经过必要的变量初始化后 进入了外围循环 也就是程序的第 7 行 第一轮循 环中 temp tempArray 0 1 4 index i 0 程序运行到第 15 行 也就是进入了内层循环 内层循环的主要任务是从第 i 1 个元素之后找到一个最大的效益并保存此时的下标 到了第 24 行后 就开始对 w i 进行排序 问题就在这里了 排序后的 w i 1 6 1 6 1 5 因此对 w i 排序后就既改变了 w i 的原 有顺序 还改变了 w i 的原来值 据此 做出一些修改 得到了如下的一段代码 1 void sort float tempArray int sortResult int n 2 int i 0 j 0 int index 0 k 0 56 for i 0 i n i 对映射数组赋初值 0 7 sortResult i 0 10 for i 0 i n i 12 float swapMemory 0 float temp temp tempArray i index i for j i j n j 20 if temp tempArray j index j 2728 if sortResult index 0 29 sortResult index k 31 for i 0 i n i 35 if sortResult i 0 37 sortResult i k 39 return 修改后最大的一个改变是没有继续沿用直接对 w i 排序 而是用 w i 的一个映射数组 sortResult i sortResult i 中元素值存放的是根据效益计算得 w i 的大小顺序 这样 w i 原有 的值和位置都没有改变 从而使算法得以实现 至于有没有更好的实现版本 还在探索中 include define MAXSIZE 100 假设物体总数 define M 20 背包的载荷能力 算法核心 贪心算法 void GREEDY float w float x int sortResult int n float cu M int i 0 int temp 0 for i 0 i n i 准备输出结果 x i 0 for i 0 i cu break x temp 1 若合适则取出 cu w temp 将容量相应的改变 if i n 使背包充满 x temp cu w temp return void sort float tempArray int sortResult int n int i 0 j 0 int index 0 k 0 for i 0 i n i 对映射数组赋初值 0 sortResult i 0 for i 0 i n i float temp tempArray i index i 找到最大的效益并保存此时的下标 for j 0 j n j if temp tempArray j index j 对 w i 作标记排序 if sortResult index 0 sortResult index k 修改效益最低的 sortResult i 标记 for i 0 i n i if sortResult i 0 sortResult i k return 得到本算法的所有输入信息 void getData float p float w int n int i 0 printf please input the total count of object scanf d n printf Please input array of p n for i 0 i n i scanf f printf Now please input array of w n for i 0 i n i scanf f return void output float x int n int i printf n nafter arithmetic data advise method n for i 0 i n i printf x d t i printf n for i 0 i n i printf 2 3f t x i return void main