4block.txt

2D single bin packing 问题的4Block算法

// 做4-Block //
void BlockManager::Creat4_Block(const Volume& Vol,BlcGroup& rBlcGroup,Goods rGoods,int GoodsNum)
{
	bool bNull=true;
	int i=0,j=0,XL=Vol.m_iXL,YL=Vol.m_iYL,ZL=Vol.m_iZL,tGoodsNum=GoodsNum,
		MaxXNum=0,MaxYNum=0,MaxZNum=0,
		MaxNum=0,tMaxNum=0,MinXL=0,
		GoodsL,GoodsW,GoodsH,
		XNum[4],YNum[4],MXNum[4],MYNum[4];
	Block tBlock;
	BlcGroup tBlcGroup,endBlcGroup;
	tBlcGroup.m_pSGL=rBlcGroup.m_pSGL;

	for(j=0;j<6;j++)
	{
		if(rGoods.m_iRotate==1&&j!=0)
			break;
		if(rGoods.m_iRotate==0&&j!=0&&j!=2)
			continue;
		bNull=true;
		GoodsNum=tGoodsNum;
		rGoods.GetRotate(j,GoodsL,GoodsW,GoodsH);
		MaxXNum=XL/GoodsL;
		MaxYNum=YL/GoodsW;
		if(ZL/GoodsH>0)
		{
			if(m_iLoadType==0)
			{
				GoodsNum/=ZL/GoodsH;
				if(GoodsNum==0)
					continue;
			}
			MaxZNum=1;
		}
		else
		{
			MaxZNum=0;
			continue;
		}
			
		if(MaxXNum==0||MaxYNum==0||MaxZNum==0)
			continue;
			
		// 做4-Block //
		MinXL=1000000;
		{
			MaxNum=0;	
			{
				for(YNum[0]=MaxYNum;YNum[0]>=1;YNum[0]--)
				{
					// 货物个数对第1block x方向个数的限制 //
					MXNum[0]=int(GoodsNum/(MaxZNum*YNum[0]));
					// 空间x长度对第1block x方向个数的限制 //
					if(MXNum[0]>MaxXNum)
						MXNum[0]=MaxXNum;
					// 根据空间y长度和第1block y方向个数得到第2block y方向个数 //
					YNum[1]=int(YL-YNum[0]*GoodsW)/GoodsL;

					for(XNum[0]=MXNum[0];XNum[0]>=1;XNum[0]--)
					{
						// x,y须同时为0 //
						if(YNum[1]==0)
							MXNum[1]=0;
						else
						{
							// 货物个数对第2block x方向个数的限制 //
							MXNum[1]=int((GoodsNum-(XNum[0]*YNum[0])*MaxZNum)/(MaxZNum*YNum[1]));
							// 第2block x长度不得超过第1block(由于对称性,可以这样设定) //
							if(MXNum[1]*GoodsW>XNum[0]*GoodsL)
								MXNum[1]=(XNum[0]*GoodsL)/GoodsW;
						}
							
						for(XNum[1]=MXNum[1];XNum[1]>=0;XNum[1]--)
						{
							// x,y须同时为0 //
							if(YNum[1]>0&&XNum[1]==0)
								continue;
							// 货物个数对第3block x方向个数的限制 //
							MXNum[3]=int((GoodsNum-(XNum[0]*YNum[0]+XNum[1]*YNum[1])*MaxZNum)/MaxZNum);
							// 空间x长度和第2Block的长度对第3block x个数的限制 //
							if(MXNum[3]>(XL-XNum[0]*GoodsL)/GoodsW)
								MXNum[3]=(XL-XNum[0]*GoodsL)/GoodsW;
							for(XNum[3]=MXNum[3];XNum[3]>=0;XNum[3]--)
							{
								// 如果底面之和大于容器底面的90%，则X取最大者 //
								if(GoodsNum*GoodsL*GoodsL*10>=XL*YL*9&&XNum[3]<MXNum[3])
									break;
								if(XNum[3]==0)
									MYNum[3]=0;
								else
								{
									MYNum[3]=YL/GoodsL;
									// 货物个数对第3block y方向个数的限制 //
									if(MYNum[3]>int((GoodsNum-(XNum[0]*YNum[0]+XNum[1]*YNum[1])*MaxZNum)/(MaxZNum*XNum[3])))
										MYNum[3]=int((GoodsNum-(XNum[0]*YNum[0]+XNum[1]*YNum[1])*MaxZNum)/(MaxZNum*XNum[3]));
								}
								for(YNum[3]=0;YNum[3]<=MYNum[3];YNum[3]++)
								{
									// x,y须同时为0 //
									if(XNum[3]>0&&YNum[3]==0)
										continue;
									// 货物个数对第3block y方向个数的限制 //
									MYNum[2]=int((GoodsNum-(XNum[0]*YNum[0]+XNum[1]*YNum[1]+XNum[3]*YNum[3])*MaxZNum)/MaxZNum);
									// 空间y长度和第4Block的y长度对第3block y个数的限制 //
									if(MYNum[2]>(YL-YNum[3]*GoodsL)/GoodsW)
										MYNum[2]=(YL-YNum[3]*GoodsL)/GoodsW;
									for(YNum[2]=0;YNum[2]<=MYNum[2];YNum[2]++)
									{
										// x,y须同时为0 //
										if(YNum[2]==0)
											XNum[2]=0;
										else
										{
											// 货物个数对第3block x方向个数的限制 //
											XNum[2]=int((GoodsNum-(XNum[0]*YNum[0]+XNum[1]*YNum[1]+XNum[3]*YNum[3])*MaxZNum)/(MaxZNum*YNum[2]));
											// 空间x长度和第2Block的长度对第3block x个数的限制 //
											if(XNum[2]>(XL-XNum[1]*GoodsW)/GoodsL)
												XNum[2]=(XL-XNum[1]*GoodsW)/GoodsL;
										}
										//for(XNum[2]=0;XNum[2]<=MXNum[2];XNum[2]++)
										{
											// 防止1,3Block重叠 //
											if(XNum[0]*GoodsL+XNum[2]*GoodsL>XL&&YNum[2]*GoodsW>YNum[1]*GoodsL)
												break;
											if(YNum[0]*GoodsW+YNum[2]*GoodsW>YL&&XNum[2]*GoodsL>XNum[3]*GoodsW)
												break;
											// 摆放类型是"4-Block" //
											tBlcGroup.m_iBlockType=4;
											// 生成4-Block
											MakeBlcGroup(Vol,tBlcGroup,XNum,YNum,GoodsL,GoodsW,GoodsH,MaxZNum);
											// 作出的Block不合适 //
											if(tBlcGroup.bNoOK4_Block(Vol))
												continue;
											if(m_iLoadType==0)
											{
												tBlcGroup.SetZNum(ZL/GoodsH);
											}
											// 这个4block是否比前一个合适
											if(CompareBlcGroup_same(tBlcGroup,endBlcGroup))
											{
												endBlcGroup=tBlcGroup;
												bNull=false;
											}
										}
									}
								}
							}
						}
					}
				}
			}
		}
		if(bNull)
			continue;
		if(CompareBlcGroup_same(endBlcGroup,rBlcGroup))
		{
			rBlcGroup=endBlcGroup;
		}
	}
}