多个约束条件下的二维装箱问题——寻找《开罗拉面店》最优布局之代码解析（一）

介绍

本代码是用C#实现的。在开始代码解析之前，先把要用到的数据贴出来：

在《开罗拉面店》里，是以左方向为x轴正方向，下方向为y轴正方向的，为了便于咱们计算，咱们可以将值顺时针旋转180°，变成咱们熟悉的坐标系，这样处理完再旋转回去就行。而这里的入口位置，则是相对于店铺左下角（也就是靠近原点的那一个方向）的格子的位置，举例说明：

这个店铺的入口相对于左下角那一格的位置，往左1格，往上4格，所以入口位置是（1，4）。

很容易可以计算出总共有 种排列情况，咱们的任务就是从这些排列情况中找到最优解！任务很艰巨是不是？

店铺类：Store

属性

Store类除了要有id、宽度、高度、入口位置之外，还要记录自己的位置，方便起见，以左下角那一格的坐标作为本店的位置；为了计算方便，还要储存本店扩大一行一列之后得到的矩形。

/// <summary>
/// 拉面店ID
/// </summary>
public int id; 

/// <summary>
/// 拉面店左下角坐标
/// </summary>
public Point point; 

/// <summary>
/// 拉面店高度
/// </summary>
public int height; 

/// <summary>
/// 拉面店宽度
/// </summary>
public int width; 

/// <summary>
/// 拉面店门的位置
/// </summary>
public Point door; 

/// <summary>
/// 拉面店覆盖区域
/// </summary>
public Rectangle area;

方法

1. 判断店铺之间是否有重叠

这是与约束条件2对应的方法，在用BL算法排兵布阵的时候要判断扩大后的店铺有没有重叠，在铺完扩大后的店铺之后还要判断没扩大的店铺有没有重叠，所以需要写多个成员函数分别判断。

/// <summary>
/// 判断自己与另一个拉面店（扩大后的）是否会重叠
/// </summary>
/// <param name="box">另一个拉面店</param>
/// <returns>若重叠则返回false，不重叠则返回true</returns>
public bool overlap(Store box)
{
    if ((point.X + area.Width-1 < box.point.X || point.X > box.point.X + box.area.Width-1) ||
        (point.Y + area.Height-1 < box.point.Y || point.Y > box.point.Y + box.area.Height-1))
    {
        return true;
    }
    return false;
}

/// <summary>
/// 判断自己与另一个拉面店是否会重叠
/// </summary>
/// <param name="box">另一个拉面店</param>
/// <returns>若重叠则返回false，不重叠则返回true</returns>
public bool overlap_pro(Store box)
{
    if ((point.X + width-1 < box.point.X || point.X > box.point.X + box.width-1) ||
        (point.Y + height-1 < box.point.Y || point.Y > box.point.Y + box.height-1))
    {
        return true;
    }
    return false;
}

/// <summary>
/// 判断本店与其他所有店是否有重叠
/// </summary>
/// <param name="ans">其他所有店</param>
/// <returns>有一个重叠就返回false，全部不重叠返回true</returns>
public bool if_available(List<Store> ans)
{
    bool flag = true;
    for (int i = 0; i < ans.Count; i++)
    {
        if (!overlap(ans[i]))
        {
            flag = false;
            break;
        }
    }

    return flag;
}

2. 深复制

在C#里，自定义类作为参数传递的时候默认是传地址的，但是在后面有一些函数在处理的时候是希望传值的（之后会详细说明），所以需要写一个深复制函数。

/// <summary>
/// 深复制
/// </summary>
/// <returns>本店深复制后得到的新店</returns>
public Store Clone()
{
    Store ans = new Store(id, new Point(point.X, point.Y), width, height, new Point(door.X, door.Y));
    return ans;
}

3. 旋转

对应于约束条件7的成员函数。

/// <summary>
/// 旋转
/// </summary>
public void rotate()
{
    int t = height;
    height = width;
    width = t;
    door = new Point(door.Y, door.X);
    area = new Rectangle(new Point(0, 0), new Size(width + 1, height + 1));
}

4. BL算法与改进

实现BL算法的第一步是将店铺放到右上角边界的位置，所以需要判断右上角边界那个位置能不能放得下，会不会和其他店铺重叠，如果能放得下的话，就可以开始玩“俄罗斯方块”了。对于BL算法，店铺需要判断能往下多少格，往左多少格；对于BL的改进算法，可以把往下移动和往左移动合并成一个动作。

/// <summary>
/// 判断本店能否在当前位置填充
/// </summary>
/// <param name="W">当前位置横坐标</param>
/// <param name="H">当前位置纵坐标</param>
/// <param name="ans">已填充的拉面店</param>
/// <returns>可以填充返回true，不能填充返回false</returns>
public bool set(int W, int H, List<Store> ans)
{
    point.X = W - area.Width;
    point.Y = H - area.Height;
    return if_available(ans);
}
/// <summary>
/// 向下移动
/// </summary>
/// <param name="store">当前已填充的拉面店</param>
/// <returns>可以移动的最大步数</returns>
public int go_down(List<Store> store)
{
    int move = 0;
    for (int i = 0; i < store.Count; i++)
    {
        if (area.Width + point.X > store[i].point.X && point.X < store[i].area.Width + store[i].point.X &&
            point.Y >= store[i].point.Y + store[i].area.Height)
        {
            int l = store[i].point.Y + store[i].area.Height;
            if (move < l)
            {
                move = l;
            }
        }
    }

    move = point.Y - move;
    point.Y -= move;
    return move;
}

/// <summary>
/// 向左移动
/// </summary>
/// <param name="store">当前已填充的拉面店</param>
/// <returns>可以移动的最大步数</returns>
public int go_left(List<Store> store)
{
    int move = 0;
    for (int i = 0; i < store.Count; i++)
    {
        if (area.Height + point.Y > store[i].point.Y && point.Y < store[i].area.Height + store[i].point.Y &&
            point.X >= store[i].point.X + store[i].area.Width)
        {
            int l = store[i].point.X + store[i].area.Width;
            if (move < l)
            {
                move = l;
            }
        }
    }

    move = point.X - move;
    point.X -= move;
    return move;
}

/// <summary>
/// BL算法加强版
/// </summary>
/// <param name="store">当前已填充的拉面店</param>
/// <returns>可以移动的最大步数</returns>
public Point BL_plus_move(List<Store> store)
{
    int down = 0;
    int left = 0;
    for (int i = 0; i < store.Count; i++)
    {
        if (point.X + area.Width > store[i].point.X && point.X < store[i].point.X + store[i].area.Width &&
            point.Y >= store[i].point.Y + store[i].area.Height)
        {
            int l = store[i].point.Y + store[i].area.Height;
            if (down < l)
            {
                down = l;
                left = store[i].point.X;
            }
        }
    }

    down = point.Y - down;
    point.Y -= down;
    int move = 0;
    for (int i = 0; i < store.Count; i++)
    {
        if (point.Y + area.Height > store[i].point.Y && point.Y < store[i].point.Y + store[i].area.Height &&
            point.X >= store[i].point.X + store[i].area.Width)
        {
            int l = store[i].point.X + store[i].area.Width;
            if (move < l)
            {
                move = l;
            }
        }
    }

    left = Math.Min(point.X + area.Width - left, point.X - move);
    point.X -= left;
    return new Point(down, left);
}

至此一个简单的Store类就基本实现了，接下来就是个体类的实现。