集装箱的装箱问题.doc

文档介绍：实验三、贪心算法的运用
——集装箱的装箱问题
系别:计算机系班级: 1班姓名:阙寿辉学号:22120051203884 日期:2008/06/06
问题描述:
给定一个集装箱,其长为L,宽为W和高为H,现有一批圆柱形木材,每根木材的长均为L,但是半径不同,设第i根木材半径为ri。问如何装箱,使得集装箱的空间利用率最高?例如:
二、算法思想:
本实验采用贪心算法的思想。将集装箱想象成为一个长为L、宽为W、高为H的长方体,将圆柱形木材想象成为一底面半径为ri、长为L的圆柱体。
1、首先需要对圆柱体按半径从大到小进行排序,排完序后将其分为两部分:一部分为已经放在矩形适当位置的(初始化为空),另一部分为剩下的尚未进行定位的圆柱体;
2、接着取出剩下的圆柱体中底面半径最大的一个,从左下角的坐标开始检查矩形空闲位置并判断当前圆柱体是否可以放入(判断圆柱体底面圆的圆心距是否合适,以及底面面积是否超过了空闲矩形的边框)。若可以,则放入之,并标记当前放入的圆柱体,记下其坐标;
3、接下来再将剩余的圆柱体取出,重复步骤2直至矩形空间中不再能够容纳下剩余圆柱体中(如果还有剩余的话)底面半径最大的一个圆柱体;
4、算法结束。
三、具体实现:
1、struct Circle_wood //圆柱形木头的数据结构
{
double x,y,r;
int sel; //判断是否和别人相交
}cr[MAXNUM];
2、double dis(Circle_wood a,double x,double y) //两个圆圆心距
{
return sqrt((-x)*(-x)+(-y)*(-y));
}
3、int sort(Circle_wood *wood,int n)//按圆柱半径由大到小排序
{
Circle_wood a;
int j;
for(int i=0;i<columnum;i++)
{
a=wood[i];
j=i-1;
while(j>=0 && wood[j].r<)
{
wood[j+1]=wood[j];
j=j-1;
}
wood[j+1]=a;
}
return 0;
}
4、int put(int now,double tx,double ty)//判断在位置(tx,ty)是否可以放下
{
if(tx<cr[now].r || tx+cr[now].r>W || ty<cr[now].r || ty+cr[now].r>H)
return 0; //不能放下,越界
for(int i=0;i<now;i++)
if(cr[i].sel)//判断是否和别人相交
if(dis(cr[i],tx,ty)<cr[i].r+cr[now].r) //相交
return 0;
return 1;
}
5、void check(int now)//为第now个木头找位置
{
double t,dx,dy;
for(int i=0;i<now;i++)
if(cr[i].sel)//对每个已插入的木头
{
t=cr[i].r+cr[now].r;
for(int j=0;