实验报告四：用贪心算法优化的石板切割问题

实验报告四：用贪心算法优化石板切割问题

一、 实验要求

给出一长度、高度均已知的木板，给出一系列长度、高度的目标板。

要求：

•目标板不能旋转，目标板长宽必须与木板长宽对应。•必须沿长边短边一刀切，每一次切割将木板分割为两个矩形。•目标板的一角应与木板一角重合。•为简化问题，题中所给的长宽均为整数。请给出木板利用率最高的切割方案。

二、问题分析与方案设计

本题的解决方案是完全原创的。

贪心算法设计综述

贪心是一种通过寻求局部最优解来获得全局最优解（或全局最优近似解）的算法，因此，根据贪心的定义很容易联想到此题的贪心解法为：将所有小目标块按照面积排序，根据面积大小，进行选择，每一步选择当前最大的一个，从而每一步都是局部最优解，这个算法看起来正确，但细细深究，其实不然，如下图：

若要在橙色的木板上切割①②③④⑤五个石板，显然，石板⑤是最大的，但倘若第一步就使用贪心算法，会立即选择⑤，而得不到其他可能的结果，从图像中可以看出，直接选择⑤得到的切割率小于100%，而选择①②③④得到的切割率却为100%，因此得到了一个错误的答案，这个特例告诉我们，不能直接使用选取最大面积的方式作为贪心策略。

经过进一步思考，我发现，特例中一开始直接选择⑤会导致其他目标板失去“出场机会”，有没有办法去保证其他目标板的“出场机会”呢？其实是有的。

每一种可行的切割方案中，一定可以找出一块最大的块，最佳可行的切割方案中的最大的目标块，并不一定是所有目标块中最大的目标块，因此，我们可以考虑对所有目标块使它作为最大块，然后进行枚举，这样操作后，我们保证了每一块都能有至少一次“出场机会”，然后对他们取最大值，就可以得到贪心策略算法的（近似）最优解。这样的枚举方式涵盖了所有可能的切割方法。

这样得到的最优解是全局最优解吗？由于纵切与横切的存在，本实验报告代码得到的并非全局最优解，与张德富老师的论文结果进行比较，得到在50、100等级的数据量上，得到的结果误差小于5%，甚至在某些情况下得到了更优的解决方案，但在10000数量级的目标块下，张德富老师的有一个数据可以得到100% 的测试结果，而本算法只能得到65.9%，至于这个问题，可以参考深度学习的思想去尝试进行解决，通过增加运算量来尽可能的获得全局最优解，这一部分将其写在了未进行的优化部分中。

结构

本题我使用了两个struct结构体、两个子函数、使用到了STL中的vector、bitset和sort排序算法，下面一一介绍他们的功能：

---

struct Stone:

struct Stone
{
    int x, y;
    int s;
 
 
    bool operator<(const Stone &s2) const
    {
        return s < s2.s;
    }
} stone[N];

这一个结构体用于存放目标块的信息，且其中重载了小于运算符，使得stone数组可以使用sort算法直接排序。

---

struct subStone:

struct subStone
{
    Stone substone[4];
    bitset<4> key;
};

这一个结构体用于存放切割下来的四个子块以及他们的“开关”

---

两个STL容器的作用：

bitset : 用于表示已经切割完毕的石板编号
vector : 建立subStone数组，存放当前有的子板

---

子函数divide：

bool divide(int i)
{
 
 
    if (st.empty())
        return false;
    for (int k = st.size() - 1; k >= 0; k--) //从小往大
        for (int j = 0; j < 4; j++)
        {
            if (st[k].key[j])
                ;
            else
                continue;
            if (st[k].substone[j].x < stone[i].x || st[k].substone[j].y < stone[i].y)
                continue;
            //能切
            if (j == 0 || j == 1)
                st[k].key[2] = st[k].key[3] = 0; //切割方式固定了
            else
                st[k].key[0] = st[k].key[1] = 0;
            subStone tmp;
            tmp.substone[0].x = st[k].substone[j].x;
            tmp.substone[0].y = tmp.substone[2].y = st[k].substone[j].y - stone[i].y;
            tmp.substone[1].x = tmp.substone[3].x = st[k].substone[j].x - stone[i].x;
            tmp.substone[1].y = stone[i].y;
            tmp.substone[2].x = stone[i].x;
            tmp.substone[3].y = st[k].substone[j].y;
            tmp.key.set();
            st.push_back(tmp);
            st[k].key[j] = 0;
            return true;
        }
    return false;
}

divide的功能是尝试对目标板i在当前的子板范围内进行切割，倘若能够切割返回true并修改相关子板信息，倘若不能切割，则返回false；

---

select子函数：

int select(int i, int mxx, int mxy)
{
    used.reset();
    st.clear();
    int s = 0;
    if (mxx < stone[i].x || mxy < stone[i].y)
        return 0; //最大的不能被选中，return 0
    subStone tmp;
    tmp.substone[0].x = mxx;
    tmp.substone[0].y = mxy;
    tmp.key[0] = 1;
    st.push_back(tmp);
    for (int k = i; k >= 0; k--)
        if(divide(k))
        {
            s += stone[k].s;
            used[k] = 1;
        }
    return s;
}

select子函数用于返回以板块i为最大板块时可以切割的最大面积。

---

特殊算法解释

如何完成横切与竖切

本实验中，不再特别地考虑横切与竖切，只考虑能否将当前的最大石板完成切割，那具体如何进行？如下图：

•石板刚切完形成的4个新小石板均是存在的（对应横竖切都是可能的）•下一次循环检查后，倘若能够使用小石板，小石板被切割，状态应该修改为不存在•一旦有小石板因为切割不存在，那么，根据上一块小石板产生的原因，另外一种方式产生的小石板将标记为不存在，即，倘若substone[0]，substone[1]被使用，substone[2]，substone[3]将立即被标记为不存在。

如何完成石板选择

完成石板选择依照：“目标板stone从大选到小，待切板subStone从新选到旧”的原则进行，即遍历stone和vector数组时均按照从后往前的顺序进行。进入到每一个subStone根据其已经标记好的“开关”依次进入到每一个板中，再进行切割，形成新的子板，再加入到vector数组中，直至不再有石板或目标板。

完全代码展示（含注释）

#include <iostream>
#include <algorithm>
#include <bitset>
#include <vector>
using namespace std;
 
 
const int N = 100;//根据不同的测试数据大小选择不同的N值
struct Stone
{
    int x, y;//记录一块石板的长宽
    int s;//记录一块石板的面积
 
 
    bool operator<(const Stone &s2) const
    {
        return s < s2.s;
    }//重载小于运算符
} stone[N];
 
 
struct subStone
{
    Stone substone[4];
    bitset<4> key;
};
 
 
bitset<N> used;//记录使用过的石板
vector<subStone> st;//记录当前所有石板
 
 
bool divide(int i)
{
 
 
    if (st.empty())
        return false;//如果石板已经是空的，那就返回无法切割
    for (int k = st.size() - 1; k >= 0; k--) //从小往大
        for (int j = 0; j < 4; j++)
        {
            if (st[k].key[j])
                ;
            else
                continue;//如果key检查该板不存在，跳过
            if (st[k].substone[j].x < stone[i].x || st[k].substone[j].y < stone[i].y)
                continue;//如果不能切，跳过
            //能切
            if (j == 0 || j == 1)
                st[k].key[2] = st[k].key[3] = 0; //切割方式固定了
            else
                st[k].key[0] = st[k].key[1] = 0;//横竖切只能存在一种
            subStone tmp;
            tmp.substone[0].x = st[k].substone[j].x;
            tmp.substone[0].y = tmp.substone[2].y = st[k].substone[j].y - stone[i].y;
            tmp.substone[1].x = tmp.substone[3].x = st[k].substone[j].x - stone[i].x;
            tmp.substone[1].y = stone[i].y;
            tmp.substone[2].x = stone[i].x;
            tmp.substone[3].y = st[k].substone[j].y;
            tmp.key.set();//1111
            st.push_back(tmp);//以上步骤均为给tmp（新的子板）赋值
            st[k].key[j] = 0;
            return true;//能切，切一次就行，返回true
        }
    return false;
}
 
 
int select(int i, int mxx, int mxy)
{
    used.reset();
    st.clear();//初始化
    int s = 0;
    if (mxx < stone[i].x || mxy < stone[i].y)
        return 0; //最大的不能被选中，return 0
    subStone tmp;
    tmp.substone[0].x = mxx;
    tmp.substone[0].y = mxy;
    tmp.key[0] = 1;
    st.push_back(tmp);//放入第一块子板
    for (int k = i; k >= 0; k--)//遍历所有子板
        if(divide(k))
        {
            s += stone[k].s;
            used[k] = 1;
        }
    return s;//返回贪心最优解
}
 
 
int main()
{
    int n, maxx, maxy;
    cin >> n;
    cin >> maxx >> maxy;
    for (int i = 0; i < n; i++)
    {
        cin >> stone[i].x >> stone[i].y;
        stone[i].s = stone[i].x * stone[i].y;
    }
    //数据录入完成
    sort(stone, stone + n);//排序完成
    int maxs = 0;
    bitset<N> fused;//用于给used数组做备份
    for (int i = n - 1; i >= 0; i--)
    {
        int tmp = select(i, maxx, maxy);
        if (tmp > maxs)
        {
            maxs = tmp;
            fused = used;
        }
    }//每一次循环都得到以板块i为最大板块时的最优解
    cout << maxs << ' ' << fused.to_string() << endl;
    cout << ((double)maxs/((double)maxx*maxy));
    //输出结果
}

未进行的优化

•我们可以在Stone 结构体中添加从第一块目标块到第k块目标块的面积和，倘若我们求出的最大面积已经大于或等于了当前的目标和，说明，我们即使将所有比第k块小的目标块都切割，也得不到比当前结果更优的解，就可以直接输出结果，该逻辑实现并不困难，所以并未重新在代码中实现。•我们也可以在subStone结构体中添加一个标记量，从而可以记录在此处是横切还是纵切，然后通过一个觅踪函数，就可以输出每一块石板的切割方式以及切割路径。•为了提高得到全局最优解的概率，我们可以在审查subStone.key时引入随机数，使得我们不一定总是从横切开始检查，使得我们可以在横切竖切中随机优先检查，这样，可能得到横切竖切的不同路径，而本算法若要同时检查横切竖切，则会增加大量的复制与递归调用，我认为这可能使得算法丢失了贪心选择性质。

测试

1.使用书上的测试数据

测试数据输入：

4
4 8
3 2
2 4
1 6
4 4

测试数据输出：

24 1100
0.75

 2.使用上述例子的测试数据测试数据输入：

5
4 4
2 2
2 2
2 2
2 2
3 3

测试数据输出：

16 01111
1

    3.使用50、 100 、 10000数据量的测试数据及与张德福老师论文的比较结果