readme.txt

给定一块宽度为W的矩形板

                 实验一    零件切割问题
　　　　　 实验者：李均荣　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）。