packing.cpp

2维装箱问题实现

extern int multi_pack_opt2(int Dir,int aL,int aW,int aH,int MaxLayer,int aWt,int NeedNum,int cL,int cW,int cH,int MaxcWt,
int &RightL,int &RightW,int &DownL,int &DownW,int &CornerL,int &CornerW)
{
//输入：集装箱尺寸。产品尺寸等
//输出：集装箱所余的底面积（3块，下边块、右边块、右下角块）
int FinalNum;
int HRow ,HCol ,VRow ,VCol ,Layer ,LastLayerMinus;
int r11 ,r12 ,r21 ,r22 ;
bool HasRight=true;     //放的右边块标志。
bool HFirst=true;       //先放的H方向标志。

//----------------计算优化开始

if (aH>cH) //--层高不够
{
  HRow=0;
  HCol=0;
  VRow=0;
  VCol=0;
  goto myend;
}

	
if (Dir==0)      //  --横放纵放不限-------------------------------------------------
{   if (aL>cL || aW>cW )      //--AAA横放不下？
    {   HRow=0;
        HCol=0;

        if (aL>cW || aW>cL)	//--不可以横放,再纵放不下？
        {   VRow=0;
            VCol=0;
            goto myend ;
        }
        else	//--不可以横放但可纵放
        {   VRow=floor(float(cW)/aL);
            VCol=floor(float(cL)/aW);
            goto myend;
        }
    }
    else	//--可以横放
    {
        if (aL>cW || aW>cL)	//--可以横放,再纵放不下？
        { VRow=0;
          VCol=0;
          HRow=floor(float(cW)/aW);
          HCol=floor(float(cL)/aL);
          goto myend;
        }

                //--剩下可以横放，可以纵放，真正优化开始
        r11=cL%aL;
        r12=cL%aW;
        r21=cW%aL;
        r22=cW%aW;
        if ((r11<=r12 && r11<= r21) || (r22<=r12 && r22<= r21))		//--横放好！
        {
            HRow=floor(float(cW)/aW);
            HCol=floor(float(cL)/aL);

           //	-----二次优化，看剩余面积纵放可以放多少
            if (aW<=cL%aL)        //--是哪一块可以放？右边块
            {   VCol=floor((cL%aL)/float(aW));
                VRow=floor(float(cW)/aL);
                goto myend;
            }
            else        //--下边块
            {
                if (aL<=cW%aW)	//--下边块够
                { HasRight=false;
                  VCol=floor(float(cL)/aW);
                  VRow=floor((cW%aW)/float(aL));
                  goto myend;
                }
                else	//--下边块也不够
                { VRow=0;
                  VCol=0;
                  goto myend;
                }
            }

        }
        else	//--纵放好！
        {
            HFirst=false;
            VRow=floor(float(cW)/aL);
            VCol=floor(float(cL)/aW);

            //-----二次优化，看剩余面积横放可以放多少
            if (aL<=cL%aW)  // --是哪一块可以放？右边块
            {   HRow=floor((cL%aW)/float(aL));	//changed
                HCol=floor(float(cW)/aW);	//changed
                goto myend;
            }
            else	//--下边块
            {
                if (aW <= cW%aL)
                {  HasRight=false;
                   HRow=floor((cW%aL)/float(aW));
                   HCol=floor(float(cL)/aL);
                   goto myend;
                }
                else
                {  HRow=0;
                   HCol=0;
                   goto myend;
                }
            }


        }  	//--纵放好！
    }   //else --可以横放 end
}       //if (Dir==0)  end

if (Dir==1)
{
     VRow=0;
     VCol=0;
     HRow=floor(float(cW)/aW);
     HCol=floor(float(cL)/aL);
     goto myend ;
}


if (Dir==2)
{
     HRow=0 ;
     HCol=0;
     VRow=floor(float(cW)/aL);
     VCol=floor(float(cL)/aW);
     goto myend;
}



//----------------计算优化完成
myend:
        Layer=floor(float(cH)/aH);
        if(Layer>MaxLayer) Layer=MaxLayer;
        LastLayerMinus=0;

//	--考虑载重量约束（箱承重，和集装箱总载重量）


if (((HRow*HCol+VRow*VCol)*Layer==0 ) || (MaxcWt<aWt))
{
     LastLayerMinus=0;
     VRow=0;
     VCol=0;
     HRow=0;
     HCol=0;
     Layer=0;
     goto finalinsert;
}

 if  ((HRow*HCol+VRow*VCol)*Layer > floor(MaxcWt/float(aWt)) )
{
    float tmpd;   		//--没办法，只好用float导一下，否则ceiling结果不对！
    tmpd=floor(MaxcWt/float(aWt));
    tmpd=tmpd/(HRow*HCol+VRow*VCol);
    Layer=ceil(tmpd );	       //	--can not be floor()+!!    LastLayerMinus=-floor(MaxcWt/float(aWt))+(HRow*HCol+VRow*VCol)*Layer;
}

			

finalinsert:
FinalNum=(HRow*HCol+VRow*VCol)*Layer-LastLayerMinus;       //最优数量

if(FinalNum>NeedNum)            //待装箱的数量xiao于最优装箱数量 ：先按照地面积清除，以Layer为倍数 ：整行或整列清除
{  int AreaNum;
   FinalNum=NeedNum;
   AreaNum= ceil(float(NeedNum)/Layer);
   if (AreaNum<=HRow*HCol)        //比HRow*HCol还小    即光 HRow*HCol就可以放下，故完全清除 VRow*VCol
   {
       HRow=ceil(float(AreaNum)/HCol);          //另外清除一部分HRow
       VCol=0;
       VRow=0;
    }
   else                         //否则清除一部分VRow
   {
       VRow=ceil((AreaNum-HRow*HCol)/float(VCol));
   }
}


   //决定剩余面积右、下、角3块

   if(HFirst&&HasRight)
   {
       DownL= aL*HCol;
       DownW= cW-aW*HRow;
       RightL= cL-aL*HCol-aW*VCol;
       RightW= aL*VRow;
       CornerL= cL-DownL;
       CornerW= cW-RightW;
   }
   if(HFirst&&!HasRight)
   {
       DownL= aW*VCol;
       DownW= cW-aW*HRow-aL*VRow;
       RightL= cL-aL*HCol;
       RightW= aW*HRow;
       CornerL=0;
       CornerW=0;
   }

   if(!HFirst&&HasRight)
   {
       DownL= aW*VCol;
       DownW= cW-aL*VRow;
       RightL= cL-aL*HCol-aW*VCol;
       RightW= aW*HRow;
       CornerL= cL-DownL;
       CornerW= cW-RightW;
   }
    if(!HFirst&&!HasRight)
   {
       DownL= aL*HCol;
       DownW= cW-aW*HRow-aL*VRow;
       RightL= cL-aW*VCol;
       RightW= aL*VRow;
       CornerL= cL-DownL;
       CornerW= cW-RightW;
   }

   if(DownL<=0||DownW<=0)
   {
      DownL=0;
      DownW=0;
    }
    if(RightL<=0||RightW<=0)
   {
      RightL=0;
      RightW=0;
    }
    if(CornerL<=0||CornerW<=0)
   {
      CornerL=0;
      CornerW=0;
    }

   return  FinalNum;

}