前言

算法课的第二次实验作业。在此浅作记录。

问题描述

stone.png

PPT上的原题如图所示，老师在课上对该题的部分条件进行了解释与修改，并且要求用递归完成此题。最终题目如下：

石材切割问题：给定一块高度无限，宽度为WW的石板。现需要从板上分别切割出nn个高度为lil_i，宽度为wiw_i的石砖。切割规则是石砖长度方向与石板的长度方向保持一致，同时满足一刀切的要求，每种石砖只切出一个。问如何切割使所使用的石材利用率较高？

这里规定输入格式：第一行一个数nn表示石砖数量；第二行一个数WW表示石板宽度；接下来nn行，每行输入3个数，分别代表石砖的编号、石砖的宽与石砖的高。

问题分析

使用一个包含石砖的编号、宽度、高度及是否已切过的判断值的结构体数组存储各个石砖的信息。在开始切割前，先对该数组按高度进行快速排序，以便每次都能取到高度最大的石砖。每次从石板直接切割时取高度最大的石砖，再对切出剩余的部分进行递归，每次按先竖切再横切的规则进行，直到余下的部分已切不出任何一个石砖。按这样进行切割，直到所有石砖均已切出为止。同时记录下每块石板切出石砖的编号与已使用石板的高度，最后将石板总面积与已使用石砖的面积（高乘宽）相除，即可得到利用率。

由于每次都取高度最大的石砖进行切割，故利用率可相对达到较大的值。

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#define MAX 131072                //存储石砖信息数量的最大值，同时代替Inf的使用
#include <stdio.h>
#include <stdlib.h>
typedef struct StoneInfo {
    int id;						//石砖的id
    int w;						//石砖的宽
    int h;						//石砖的高
    int is_used;				//该石砖是否已经切出
}StoneInfo;
StoneInfo S[MAX];
int used_area = 0, top = 0, used_h = 0;    //已经切出的石砖总面积，未切过的第一块石砖位置，已使用的高度
int n, num = 0;                            //石砖总数，目前切出的石板个数

int HeightCompare(StoneInfo* a, StoneInfo* b)    //比较石砖高度时调用的函数
{
    if (b->h - a->h)return b->h - a->h;
    else return b->w - a->w;
}
void StoneCut(int w, int h)        //石板切割函数
{
    if (h == 0 || w == 0)return;		//待切石板的宽或高为0时退出函数
    int i = top;
    if (h == MAX)						//开辟新一块石板进行切割
    {
        printf("从第%d块石板中切下的石砖id：%d ", ++num, S[i].id);
        S[i].is_used++;					//该石砖已切出
        used_h += S[i].h;				//开辟相同高度的石板
        used_area += S[i].w * S[i].h;	//切出面积增加
        printf("%d ", S[i].id);			//输出该切出石砖的id
        StoneCut(w - S[i].w, S[i].h);	//对剩余部分进行递归
        while (S[top].is_used)top++;	//使top指向未切过的第一块石砖的位置
        printf("\n");
        return;
    }
    while ((S[i].h > h || S[i].w > w || S[i].is_used) && i < n)i++;	//找到可切且未切过的石砖
    if (i < n)
    {
        S[i].is_used++;
        used_area += S[i].w * S[i].h;
        printf("%d ", S[i].id);
        StoneCut(w - S[i].w, h);
        StoneCut(S[i].w, h - S[i].h);
        while (S[top].is_used)top++;
    }
    return;
}

int main()
{
    int W, i;
    scanf("%d%d", &n, &W);
    for (i = 0; i < n; i++)
    {
        scanf("%d%d%d", &S[i].id, &S[i].w, &S[i].h);		//石砖数据
        S[i].is_used = 0;									//参数初始化
    }
    qsort(S, n, sizeof(StoneInfo), HeightCompare);			//按高度进行快速排序
    while (top < n)				//还有石砖未切出
        StoneCut(W, MAX);
    printf("已使用的石板总高度为：%d\n所有切出的石砖总面积为：%d\n", used_h, used_area);
    double Used_Area = used_area, Total_Area = W * used_h;	//转化为浮点数以进行利用率的运算
    printf("计算得利用率为：%lf%%", Used_Area / Total_Area * 100);
    return 0;
}

后记

在每次切割时的石砖选择上使用了贪心算法，每次都取满足条件且高度最大的石砖进行切割。这样切割所得出的利用率不一定是最高的，但可以保证在较小的时间复杂度内计算出一个较优解。当nn较小时，可以采用回溯的算法求出最优解，这里不再细述。