plane__the__cutting.rar_The Cutting_数据结构

实验一 零件切割问题 　　　　　 实验者：李均荣　04120043 一、问题描述： 　　给定一块宽度为W的矩形板，矩形板的高度不受限制。现需要从板上分别切割出n个高度为hi，宽度为wi的矩形零件。切割的规则是零件的高度方向与矩形板的高度方向保持一致。问如何切割使得所使用的矩形板的高度h最小？ 　　　　 问题等价于往一个宽为W、高不限的盒子里放木板，使得所用高度最小。 二、基本思路： 先将木板用快排的方法按高度由高到底排列，然后依次放进盒子里。要放第i块时先比较剩下的宽度，如果木板宽度小于剩下的宽度，就将第i块木板放在第i-1块右边，否则垒在当前最高块的上面。然后对该层剩下的做递归调用，如此进行下去可得一个可行解。 最优解 可行解 16.txt:n=16;W=20; H=15; 31 25.txt:n=25;W=40; H=15; 22 50.txt:n=50;W=40; H=15; 19 84.txt:n=84;W=225; H=166; 191 110.txt:n=110;W=425; H=52; 62 156.txt:n=156;W=475; H=66; 78 关键代码如下： int DivideBoard(struct graph a[],int i,int leftw,int W,int n) { if(i==n){return 1;} else { if(a[i].weith<=leftw){ H=H; leftw=leftw-a[i].weith; i++; DivideBoard(a,i,leftw,W,n); } else { H=H+a[i].height; leftw=W-a[i].weith; i++; DivideBoard(a,i,leftw,W,n); } } } 分析： 由于按顺序存放故空间浪费较大，比如若第k块较宽以至于剩余的宽度容不下，那么这块就要放到当前最高块的上方，但实际上可能存在这样的块，其高度比第k块小（排在第k块的后面），宽度也比较小，适合放在第k-1块的右边。这种做法的时间主要花费在快排上，所以时间复杂度为O（nlog n）。 改进： 在基本思路的基础上增加一步，若第k块较宽以至于不能放在第k-1块的右边，那么就从剩下的零件中找第一块适合放在该位置的零件放进去，然后将第k块放在当前最高块的上面。改进之后得到的可行解如下： 16.txt:n=16;W=20; H=15; 　26 25.txt:n=25;W=40; H=15; 　22 50.txt:n=50;W=40; H=15; 　19 84.txt:n=84;W=225; H=166; 　179 110.txt:n=110;W=425; H=52; 　61 156.txt:n=156;W=475; H=66; 　77 关键代码如下： int DivideBoard(struct graph a[],int i,int leftw,int W,int n) { int j,k; struct graph temp; if(i==n){return 1;} else { if(a[i].weith<=leftw){ H=H; leftw=leftw-a[i].weith; i++; DivideBoard(a,i,leftw,W,n); } else { j=i+1; while(j<n) { if(a[j].weith<leftw) { H=H; leftw=leftw-a[j].weith; for(k=j+1;k<n;k++) { a[k-1]=a[k]; a[k].weith=0; a[k].height=0; } break; } else { j++; } } H=H+a[i].height; leftw=W-a[i].weith; i++; DivideBoard(a,i+1,leftw,W,n); } } } 分析： 这种方法在前一种基础上对16.txt和84.txt文档的测试数据有较明显的改进，但是仍有很大的浪费空间。这种方法只是找到一块适合放在右边的木板放进去，然后就对当前最大高度以上的空间分治递归，因此改进比较小。但由于在寻找第一个适合的块，故时间复杂度增加了，为O（n*n）。