贪心算法实验-包装问题

1、课程名称：算法设计与分析 姓名实验序号：一、实验名称班级:学号实验日期 指导教师 实验成绩2013-10-28贪心算法实验-包装冋题二、实验目的及要求1、使用在线测评的算法题目评分系统来测试所写代码;2、通过直观的应用问题，加深对贪心算法的理解；三、实验环境任意C或C+编写调试工具，北京大学ICPC在线测评系统POJ四、实验内容1、登陆POJ系统，找到题号为1017的题目-包装；2、阅读题目,分析出求解该问题的思路；3、使用贪心算法，实现本题；4、进行简单测试，完成之后提交到POJ系统。五、算法描述及实验步骤贪心算法原理：贪心算法通过一系列的选择来达到子问题的解。它所做的每一步选择都是当 前状

2、态下局部最好选择，即贪心选择。这种启发式的策略虽不能总是奏效，但大 多数情况下确能达到预期目的，得到最优解。要使用贪心算法，问题必须具备两个基本要素。贪心选择性质和最优子结构 性质。贪心选择性质指所求问题的整体最优解可以通过一系列局部最优的选择， 即贪心选择来达到。通常采用自顶向下的方式进行，这样每做一次贪心选择就将 所求问题化为规模更小的子问题。当然，前提是所求问题本身的最优解包含其子 问题的最优解，即具有最优子结构性质。包装问题描述：有一个工厂生产一种长宽为 1*1、2*2、3*3、4*4、5*5、6*6的产品，这些 产品交付到客户手中都是用6*6的包裹包装。因为费用问题，工厂希望使用最少

3、 的包裹寄送给订购货物的客户。一个好的程序能够根据订单找到最少需要的包裹 数量。你被要求写这样一个程序。输入输入文件由若干行组成，每一行市一个订单，所有的订单都由6个整数组成, 分别对应1*1产品到6*6产品的需求量。输入文件的最后一行由 6个0组成。输出输出文件的每一行对应输入文件的每一行，它包含了最少需要的包裹数量。输入示例0 0 4 0 0 1 /4个3*3的产品和1个6*6的产品7 5 1 0 0 0 /7个1*1的产品、5个2*2的产品和1个3*3的产品0 0 0 0 0 0 /0 结束输出示例21/至少需要2个包裹/至少需要1个包裹实验步骤：1、建立包装问题的解题思路疋先本程序使用

4、贪心算法，也就是先给6*6的包装，在给5*5的包装， 如果有1*1的与5*5包装在一起，直到6*6的包裹空间用完，继续包装 4*4的，剩余的空间又可以包装2*2或者1*1的，3*3的一个包裹可以 装4个，如果没有4个可以装，再装2*2的或1*1的。最后在装2*2的， 1*1的。总的来说就是先让大的装，装了剩余的空间用可以装的产品再 装。2、构造算法框架 把65的分好把1*1分配在5*5里面把4的分好 把2*2的分在4*4的空间里面 把1的分在4*4的空间里 把6 5 43的分好 给2*2的分在3*3的空间如还有空间则把1分在3的空间3、分析出算法复杂度算法的复杂度为O(n log n)六、调试

5、过程及实验结果叫=C:wi ndoste m 3 ADebu g21.Ke0 9PressQ any6key to continue七、总结在动态规划算法中，每步所做的选择往往依赖于相关子问题的解。 因而只有 在解出相关子问题后，才能做出选择。而在贪心算法中，仅在当前状态下做出最 好的选择，即局部最优选择。八、附录#in clude#in clude#in cludevcstri ng int nu m4=0,5,3,1; int box7;int mai n()/freo pen (i np ut.txt,r,stdi n);while(1)int tmp=0;for(i nt i=1;ia2)an s+=(box2-a2+8)/9;int a仁a ns*36-box6*36-box5*25-box4*16-box3*9-box2*