实验四回溯算法应用.doc

文档介绍：实验四:回溯算法的应用
——零件切割问题
系别:计算机系班级: 1班姓名:阙寿辉学号:22120051203884 日期:2008/06/18
一、问题描述:
给定一块宽度为W的矩形板,矩形板的高度不受限制。现需要从板上分别切割出n个高度为hi,宽度为wi的矩形零件。切割的规则是零件的高度方向与矩形板的高度方向保持一致。问如何切割使得所使用的矩形板的高度h最小?
例如:
请设计出一个回溯算法:
,能输出切割所需要的实际高度

二、算法思想:
首先将零件按高度从大到小的顺序排列好,在排序的时候本实验采用的是快排。选择零件中高度最高的一块,将该零件按照高度方向放入矩形,零件的左下角与矩形的左下角重合。这样,整个矩形空间已经被划分为三个部分:已经放上零件的一部分、所放零件的右部和所放零件的上部。然后在所放零件的右部和上部对剩余的零件采用回溯法,确定其放在哪个位置(此过程中应该考虑会不会越界)。在回溯过程中计算当前枝以后可能的最大高度上界。如果该上界比当前的最大高度还高,则剪去该枝,直至所有的零件都被放入矩形。最后计算出放入的最左各层零件最大高度之和。
三、具体实现:
1、木板和木块(将零件和矩形抽象)的数据结构定义如下:
typedef struct MuKuai{ //木块结构体定义
float h; //木块高度
float w; //木块宽度
struct MuKuai *next; //木块链表
}MuKuai;
typedef struct MuBan{ //木板结构体定义
float x; //木板的左下脚横坐标
float y; //木板的左下脚纵坐标
float h; //木板高度
float w; //木板宽度
struct MuBan *next;//木板链表
}MuBan;
2、算法中用到的各变量声明如下:
MuKuai *headMuKuai = NULL; //木块链表头指针
MuBan *headMuBan = NULL; //木板链表头指针
MuBan *A = NULL; //用于存放最终结果
MuBan *X; //用于保存当前找到的路径
MuBan *bestX; //用于保存当前找到的最佳路径
int n; //木块总个数
int Line; //用于控制递归深度
float W; //木板宽度
float h = 0; //当前找到的路径木板总高度
float besth = 35767; //最佳路径木板高度
int x = 0; //用于调整屏幕的相对坐标
int k = 0; //用于动态显示木块变化
float **C = NULL; //定义颜色数组头指针
3、各函数功能如下:
1. float **CreatFloatArray_2(float **Head,int m,int n)
{//根据输入的二维数组行和列动态创建二位数组,返回数组指针
int i,j;
float *p=NULL;
if( !(m > 0 && n > 0) )
{ //判断维度是否正确
printf("错误的数组维度\n");
return NULL;