0908060085-何安贵-算法第三次实验.docxVIP

贵州大学计算机科学与技术学院计算机科学与技术系上机实验报告课程名称：算法设计与分析班级：计科093实验日期：2011-12-9姓名：何安贵学号：0908060085指导教师：程欣宇实验序号：三实验成绩：一、实验名称贪心算法实验 - 包装问题二、实验目的及要求1、使用在线测评的算法题目评分系统来测试所写代码；2、通过直观的应用问题，加深对贪心算法的理解；三、实验环境任意C或C++编写调试工具，北京大学ICPC在线测评系统POJ四、实验内容1、登陆POJ系统，找到题号为1017的题目-包装；2、阅读题目，分析出求解该问题的思路；3、使用贪心算法，实现本题；4、进行简单测试，完成之后提交到POJ系统。五、算法描述及实验步骤贪心算法原理：贪心算法通过一系列的选择来达到子问题的解。它所做的每一步选择都是当前状态下局部最好选择，即贪心选择。这种启发式的策略虽不能总是奏效，但大多数情况下确能达到预期目的，得到最优解。要使用贪心算法，问题必须具备两个基本要素。贪心选择性质和最优子结构性质。贪心选择性质指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。通常采用自顶向下的方式进行，这样每做一次贪心选择就将所求问题化为规模更小的子问题。当然，前提是所求问题本身的最优解包含其子问题的最优解，即具有最优子结构性质。包装问题描述：有一个工厂生产一种长宽为1*1、2*2、3*3、4*4、5*5、6*6的产品，这些产品交付到客户手中都是用6*6的包裹包装。因为费用问题，工厂希望使用最少的包裹寄送给订购货物的客户。一个好的程序能够根据订单找到最少需要的包裹数量。你被要求写这样一个程序。输入输入文件由若干行组成，每一行市一个订单，所有的订单都由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结束输出示例2 //至少需要2个包裹1 //至少需要1个包裹实验步骤：1、建立包装问题的解题思路建立包装问题的解题思路主要来自于贪心算法，每次往包裹里包装产品的时候，按照产品的尺寸由大到小依次包装，每次的包装都要把包装盒塞满才换下一个包装盒，直到所有产品的包装玩，这样得到的包裹数量一定就是最少的。2、构造算法框架建立求解最少包裹数的函数Packet( ),它有六个参数a1、a2、a3、a4、a5、a6分别表示六种不同规格的产品的数量，函数中定义一个变量i用以记录包裹的数量最后返回，函数中分别对a1、a2、a3、a4、a5、a6进行判断，即使地更新i的值和a1、a2、a3、a4、a5、a6的剩余量，最后得到最少包裹数i并将它的值返回。3、分析出算法复杂度该算法的复杂度与订单的数量有关，就等于订单的数量。六、调试过程及实验结果1.调试过程：在实验调试的过程中出现了不少的问题，开始算法写好的时候调试，有错误while（）语句没写对，问题解决之后，输入数据运行后没有错误了，但是没有结果，仔细检查程序之后发现，输出变量写错了a[j]写成了a[i]，后来运行题目给的例子，结果对了，可是在网上提交测试的时候通不过，想想应该是算法错误了，之后用了很大的输入数据，把程序设了断点，一步步跟踪调试，一点点的修正了算法的错误，这些错误在输入数据很小的时候对结果是没有影响的，所以开始的结果才会没有错。2.实验结果：七、总结1.通过这次的包装实验是自己的贪心算法的应用了一定的了解，此外对贪心算法的原理，代码编写进一步熟悉；2.通过这次实验的调试过程，让我更加认识到有时候程序的出的结果是对的并不代表你的算法就是正确的，也许你的算法只能对部分的数据求出正确结果，想要验证算法的正确性必须测试多组的数据而且数据还得有代表性；3.在测试的时候最好使用单步跟踪，了解算法的执行过程，判断其正确性。八、附录// 贪新算法.cpp : 定义控制台应用程序的入口点。//#include stdafx.h#includeiostreamusing namespace std;int Packet(int a1,int a2,int a3,int a4,int a5,int a6){int i=0;if(a6!=0)i=a6;if(a5!=0){i=i+a5;if(a1-a5*(36-25)=0)a1=a1-a5*(36-25);elsea1=0;}if(a4!=0){ i=i+a4;if(a2-a4*5=0)a2=a2-a4*5;else{if(a1-(a4*5-a2)