實驗一    零件切割問題
　　　　　 實驗者：李均榮　04120043
一、問題描述：
　　給定一塊寬度為W的矩形板，矩形板的高度不受限制。現(xiàn)需要從板上分別切割出n個高度為hi，寬度為wi的矩形零件。切割的規(guī)則是零件的高度方向與矩形板的高度方向保持一致。問如何切割使得所使用的矩形板的高度h最小？

　　　　 

    問題等價于往一個寬為W、高不限的盒子里放木板，使得所用高度最小。

二、基本思路：
    先將木板用快排的方法按高度由高到底排列，然后依次放進盒子里。要放第i塊時先比較剩下的寬度，如果木板寬度小于剩下的寬度，就將第i塊木板放在第i-1塊右邊，否則壘在當前最高塊的上面。然后對該層剩下的做遞歸調(diào)用，如此進行下去可得一個可行解。
                  最優(yōu)解    可行解  
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文檔的測試數(shù)據(jù)有較明顯的改進，但是仍有很大的浪費空間。這種方法只是找到一塊適合放在右邊的木板放進去，然后就對當前最大高度以上的空間分治遞歸，因此改進比較小。但由于在尋找第一個適合的塊，故時間復雜度增加了，為O（n*n）。