《2022年装箱问题C语言实现定义 .pdf》由会员分享，可在线阅读，更多相关《2022年装箱问题C语言实现定义 .pdf（10页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、算法分析题目：装箱（Bin Packing）问题院别：数学与计算科学学院专业：信息与计算科学姓名：蒋文明学号：0800710313 指导老师：宁黎华日期：2011.06.9 名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 10 页 -目 录一、问题描述.1 二、问题分析.1 三、代码实现.2 四、测试结果.3 五、心得体会.4 六、源程序.4 名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 10 页 -1 一、问题描述一个工厂制造的产品形状都是长方体，它们的高度都是h，长和宽都相等，一共有六个型号，他们的长宽分别为1*1，2*2，3*3，4*4，5*5，6*6.这些
2、产品通常使用一个 6*6*h 的长方体包裹包装然后邮寄给客户。因为邮费很贵，所以工厂要想方设法的减小每个订单运送时的包裹数量。他们很需要有一个好的程序帮他们解决这个问题从而节省费用。二、问题分析对于 6*6 的一个箱子来说，最多只能放一个6*6 或一个 5*5 或 4*4 的盒子，所以我们初始化需要的箱子数时就是这这几种箱子的个数和，对于3*3 的箱子来说，我们可以放一个或 2 个或 3 个或 4 个，这我们可以通过整除和取模来确定放了3*3 盒子的箱子数，再把它加入到总箱子数中，接下来我们就是把 1*1 和 2*2 的盒子塞进前面所需的箱子中，当塞不完时再来新增盒子，我们首先要将前面的箱子剩
3、余的空间统计出来，并且要以2*2的优先考虑，因为我们可以把多余的2*2 的位置变为填充4 个 1*1 的，毕竟 1*1 的只要有空间随处都可以塞。所以当我们的箱子要是装了1 个 5*5的盒子的话，那么它就只能塞1*1 的了，一个可以塞11 个 1*1 的，对于装了 4*4 的盒子的话，那么还可以装 5 个 2*2 的盒子，暂且不要去转话成1*1的，除非没办法只能装1*1 的，对于 3*3 的话就可以根据取模之后一个箱子剩下的空间了，如果一个箱子中只放了一个3*3 的，那么还剩下 3 个 3*3的空间可以放，我们知道可以放5 个 2*2 的和 7 个 1*1 的，对于放了 2 个3*3 的箱子，
4、我们剩下的空间可以放3 个 2*2 的以及 6 个 1*1 的，对于放了名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 10 页 -2 3 个 3*3 的箱子，我们只能放1 个 2*2 的和 5 个 1*1 的，这样一来我们就统计出了此时可以放2*2 以及 1*1 的空间到底有多少，接下来我们就放箱子进去，放一个就减一个，直到1*1 的和 2*2 的为 0。三、代码实现（C语言）C语言代码主要有三部分组成，main()函数、Input()和 Output()。Input()函数主要接收键盘输入的值（各型号产品的数量），将其存入数组 productn中。Output()对各种类型的
5、产品进行逻辑判断，优先让型号为6*6、5*5、4*4、3*3 的产品装入箱子，然后再将型号为2*2、1*1 的产品插入之前装的箱子 2*2 的先插入，之后插入1*1 的，如果都插满了还有1*1 或 2*2 的产品，就在新开箱子将其装入，直到所有的产品都被装入箱子。最后打印输出每个箱子具体装入产品及型号的情况和总共用的箱子数。名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 10 页 -3 四、测试结果名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 10 页 -4 五、心得体会时间飞逝，转眼间一个学期又过去了，在上算法分析理论课的过程中，我对很多经典的算法有了更深层次的
6、了解。解决同一个问题有很多不同的算法，所以在选择算法的过程中要考虑很多因素，一点小小的改进程序执行的时间可能就会缩短好几倍，算法的效率成了评价一个算法好坏的不可或缺的一个标准。这次课设，我选择了装箱（Bin Packing）问题，在实例化题目和设计算法的过程中，我查阅了很多相关的资料，在此我也学到了很多有关算法设计方面的知识，程序的编写和调试也花了我很多时间，最终通过自己的努力完成了课程设计。在此，我要感谢课设的指导老师！六、源程序#include#define BOX_VAL 36#define N 6 int productN;/存放各种类型的产品数量int boxNum=0;/存放订单需
7、要的箱子数目void Input();void Output();void main()Input();Output();printf(该订单需要的箱子数目为：%dn,boxNum);printf(n);名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 10 页 -5/用来输入每种产品的数量，保存在productN数组中void Input()int i;printf(Please input products information!n);for(i=0;i0)boxNum+=product5;printf(装型号为6*6 产品的箱子数为：%dn,product5);printf
8、(n);if(product40)boxNum+=product4;if(pro1-product4*11)=0)printf(装型号为5*5 和 1*1 产品的箱子数为：%dn,product4);printf(n);pro1-=product4*11;else if(pro1%11=0)printf(装型号为5*5 和 1*1 产品的箱子数为：%dn,pro1/11);printf(n);pro1=0;else printf(装型号为5*5 和 1*1 产品的箱子数为：%dn,(pro1/11)+1);printf(n);printf(只装型号为5*5 产品的箱子数为：%dn,(produ
9、ct4-(pro1/11)-1);printf(n);pro1=0;if(product30)boxNum+=product3;if(pro2-product3*5)=0)printf(装型号为4*4 和 2*2 产品的箱子数为：%dn,product3);名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 10 页 -6 printf(n);pro2-=product3*5;else if(pro2%5=0)printf(装型号为4*4 和 2*2 产品的箱子数为：%dn,pro2/5);printf(n);pro2=0;else printf(装型号为4*4 和 2*2 产品的箱
10、子数为：%dn,(pro2/5)+1);printf(n);printf(只装型号为4*4 产品的箱子数为：%dn,(product3-(pro2/5)-1);printf(n);pro2=0;if(product20)if(product2%4=0)boxNum+=product2/4;printf(只装型号为3*3 产品的箱子数为：%dn,product2/4);printf(n);else int temp=0;boxNum+=product2/4+1;printf(只装型号为3*3 产品的箱子数为：%dn,product2/4);printf(n);temp=product2%4;sw
11、itch(temp)case 1:if(pro2=6)pro2=pro2-6;printf(装型号为3*3、2*2 产品的箱子数为：%dn,1);printf(n);else pro1=27-pro2*4;pro2=0;if(pro1=4)pro2=pro2-4;printf(装型号为3*3、2*2 产品的箱子数为：%dn,1);printf(n);else pro1=18-pro2*4;pro2=0;if(pro1=2)pro2=pro2-2;printf(装型号为3*3、2*2 产品的箱子数为：%dn,1);printf(n);else pro1=9-pro2*4;pro2=0;if(pr
12、o10)if(pro2%9=0)boxNum+=pro2/9;printf(只装型号为2*2 产品的箱子数为：%dn,pro2/9);printf(n);pro2=0;if(pro1%36=0)boxNum+=pro1/36;printf(只装型号为1*1 产品的箱子数为：%dn,pro1/36);printf(n);pro1=0;else 名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 10 页 -8 boxNum+=pro1/36+1;printf(只装型号为1*1 产品的箱子数为：%dn,pro1/36+1);printf(n);pro1=0;else if(pro2*4+pro1)%36=0)boxNum+=(pro2*4+pro1)/36;printf(装型号为2*2、1*1 产品的箱子数为：%dn,(pro2*4+pro1)/36);printf(n);else boxNum+=(pro2*4+pro1)/36+1;printf(装型号为2*2、1*1 产品的箱子数为：%dn,(pro2*4+pro1)/36+1);printf(n);名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 10 页 -