零件切割问题.cpp

算法设计经典题目 零件切割问题 内附代码

#include <stdio.h>
#include <windows.h>
#include <GL/gl.h>
#include <GL/glaux.h>
#define  fileName "16.txt"

//矩形定义
typedef struct rectangle{  
	int width;		  //矩形宽度
	int high;		  //矩形高度
	float x;		  //矩形的左下顶点横坐标
	float y;		  //矩形的左下顶点纵坐标
	int flag;		  //判断切割时是否需要增加高度h
}RECTANGLE;   

//木块定义
typedef struct part{
	int width;		  //零件宽度
	int high;	      //零件宽度
	float x;	      //切割后零件左下顶点横坐标
	float y;		  //切割后零件左下顶点纵坐标
}PART;

//根据输入的二维数组行和列动态创建二位数组，返回数组指针
float **CreatFloatArray_2(float **head,int m,int n)
{
    int i,j;
    float *p=NULL;
    if( !(m > 0 && n > 0) ){                     //判断维度是否正确
		printf("数组维度出错!\n");
		return NULL;
	}
    p = (float *)malloc(sizeof(float) * m * n);  //申请总体空间
    head = (float **)malloc(sizeof(float *)*m);  //申请二级指针空间
    for(i = 0;i < m;i++)                
        head[i]=p + n * i;
    for(i = 0;i < m;i++)                  
        for(j = 0;j < n;j++)
            head[i][j] = 0;
    return head;
} 

//以下为两个比较函数，用于qsort函数
int REC_SORT(const void *a,const void *b) //矩形按高度排序
{
	RECTANGLE *REC_a = (RECTANGLE *)a;
	RECTANGLE *REC_b = (RECTANGLE *)b;
	return REC_a->high > REC_b->high ? 1:-1;
}
int PART_SORT(const void *a,const void *b) //零件按高度排序
{
	PART *Part_a = (PART *)a;
	PART *Part_b = (PART *)b;
	return Part_a->high > Part_b->high?-1:1;
}

void Cut_REC(RECTANGLE *Rec,int count,PART *Part,int *high) 
//count指向当前矩形数组的最后一块，high为当前矩形的切割高度
//Rec和Part指针分别是全局的矩形和零件数组头指针
{
	int	i;
	PART *p = Part + 1;  //下次递归的参数，从下一块矩形进入切割
	if(Part[0].high == 0)  //没有零件需要切割了,退出递归
		return ;
	for(i = 0;Rec[i].width < Part[0].width || Rec[i].high < Part[0].high;i++); //寻找合适的矩形
	count++;
	if(Rec[i].flag == 1)//判断是否需要增加切割高度
		*high += Part[0].high;
	Part[0].x  = Rec[i].x;//记录切割的左下角位置，便于图形显示
	Part[0].y  = Rec[i].y;//切割矩形并放入木板数组
	Rec[count].width = Rec[i].width;
	Rec[count].high  = Rec[i].high - Part[0].high;
	Rec[count].x = Rec[i].x;
	Rec[count].y = Rec[i].y + Part[0].high;
	if(Rec[i].flag == 1)
		Rec[count].flag = 1;
	Rec[i].width -= Part[0].width;
	Rec[i].high = Part[0].high;
	Rec[i].x += Part[0].width;
	Rec[i].y = Rec[i].y;
	Rec[i].flag = 0;
	
	//对矩形数组进行按高度的递减排序
	qsort(Rec,count + 1,sizeof(Rec[0]),REC_SORT);	
	Cut_REC(Rec,count,p,high);//递归调用
}

int count;		      //count为零件的个数
int k =1;             //用于动态显示零件变化
int x = 0;		      //用于调整opengl中屏幕的相对坐标
PART  *part = NULL;	  //零件数组定义
float **color = NULL; //定义颜色数组头指针

//以下函数为opengl图形绘制函数 ////////////////////////////////////////////////////////	
void myinit(void)                                                                    //
{                                                                                    //
    glClearColor(0.0,0.0,0.0,0.0);                                                   //
    glClear(GL_COLOR_BUFFER_BIT);
    glShadeModel(GL_FLAT);
}
void CALLBACK down(void) 
{ 
	if(k < count)
		k++;
} 
void CALLBACK myReshape(GLsizei w,GLsizei h)
{
	glViewport(0,0,w,h);
	glMatrixMode(GL_PROJECTION);
	glLoadIdentity();
	if(w<=h)
		glOrtho(-x,x,-x*(GLfloat)h/(GLfloat)w,x*(GLfloat)h/(GLfloat)w,-50.0,50.0);
	else
		glOrtho(-x*(GLfloat)h/(GLfloat)w,x*(GLfloat)h/(GLfloat)w,-x,x,-50.0,50.0);
	glMatrixMode(GL_MODELVIEW);
	glLoadIdentity();
}
void DrawMyObjects(void)
{
	int i;
	glBegin(GL_LINE_STRIP);    //绘制矩形
	glVertex2f(0.0,0.0);
	glVertex2f(0.0,2*x-0.2*x);
	glVertex2f(0.0,0.0);
	glVertex2f(x,0.0);
	glVertex2f(x,0.0);
	glVertex2f(x,2*x-0.2*x);
	glEnd();	
	for(i = 0; i < k;i++)
	{
		glColor3fv(color[i]);
		glBegin(GL_QUADS ); 
		glVertex2f(part[i].x,part[i].y + part[i].high);
		glVertex2f(part[i].x,part[i].y);
		glVertex2f(part[i].x + part[i].width,part[i].y);
		glVertex2f(part[i].x + part[i].width,part[i].y + part[i].high);
		glEnd();                                                              
	}                                                                            
}
void CALLBACK display(void)
{
	glColor3f(1.0,0.0,0.0);
	if(k == 1)
		glTranslatef(-(x * 0.5),-(x-0.1*x),0.0);//移动屏幕坐标到矩形左下方
	DrawMyObjects();
	glFlush();
}	                                                                              //
////////////////////////////////////////////////////////////////////////////////////

int main()
{
	int i,n,w,h = 0;   //w为矩形宽度，n为零件个数，h为最终矩形的切割高度
	FILE *fp;
	RECTANGLE Rec[200];//定义矩形数组
	
	printf("======================================================\n");
	printf("|                      用户须知                      |\n");
	printf("|  注意：程序运行时有两个窗口，控制台窗口和图形窗口  |\n");
	printf("|  请勿移动控制台窗口，否则会影响图形显示            |\n");
	printf("|  如已移动窗口并造成了图形显示异常，请重新运行程序  |\n");
	printf("|  请按键盘上的“向下方向键”动态显示木块            |\n");
	printf("======================================================\n");

	if(!(fp = fopen(fileName,"r"))) 
	{   //打开零件文件
		printf("打开文件%s失败!\n",fileName);
		return -1;
	}
	fscanf(fp,"%d %d",&n,&w);
	x = w;         //用于调整opengl中屏幕的相对坐标
	if(!(part = (PART *)malloc(sizeof(PART) *(n + 1))))
	{   //零件数组申请
		printf("零件数组申请失败!\n");
		return -1;
	}
	Rec[0].width = w;     //初始矩形
	Rec[0].high = 65535;  //高度为无穷大
	Rec[0].x =(float)0.0;     
	Rec[0].y =(float)0.0;
	Rec[0].flag = 1;      //为1表示切割需要增加高度
	printf("零件数据如下:\n");
	for(i = 0; i < n; i++)//读入并打印出零件数据
	{
		fscanf(fp,"%d %d",&part[i].high,&part[i].width);
		printf("%d,%d\n",part[i].high,part[i].width);
	}
	part[n].width = 0;    //放置最后一块用于标志结束
	part[n].high  = 0;	
	fclose(fp);
	qsort(part,n,sizeof(part[0]),PART_SORT); 
	Cut_REC(Rec,0,part,&h);	 
	count = n;  
	//生成颜色数组，用于绘制图形
	color = CreatFloatArray_2(color,n,3); //动态创建二位数组，用于存放颜色
	for(i = 0; i < n; i++)
	{
		color[i][0] = (rand()%3)/3.0 + 0.01;
		color[i][1] = (rand()%6)/6.0 + 0.3;
		color[i][2] = (rand()%9)/7 + 0.05;
	}
    
	//opengl函数
    /////////////////////////////////////////////////////////////////////
	auxInitDisplayMode(AUX_SINGLE|AUX_RGBA);                           //
    auxInitPosition(250,100,800,800);                                  //
    auxInitWindow("递归与分治:零件切割问题");                          //
    myinit();                                                          //
	auxKeyFunc(AUX_DOWN,down);                                         //
    auxReshapeFunc(myReshape);                                         //
    auxMainLoop(display);                                              //
    /////////////////////////////////////////////////////////////////////
	
	printf("所需的最小高度 H = %d\n",h);
	return 1;
}