qiege.cpp

解决了矩形板切割矩形材料的问题

//给定一块宽度为W的矩形板，矩形板的高度不受限制。现需要从板上分别切割出n个高度为hi，宽度为wi的矩形零件。切割的规则是零件的高度方向与矩形板的高度方向保持一致。要求求出一种切割法使得所使用的矩形板的高度h最小．用递归及分治法解此问题

#include<stdio.h>

#include <iostream>

#define MAX 1000

//定义零件结构

typedef struct block{

	int w;//宽

	int h;//高

	int visited;//是否已经被切割

}ss;

ss s[MAX];
int cut();

int h=0,n,height,width,w;

int subcut(int h1,int w1);

void main()
{

	 int i,j,flag=1;

	struct block temp;

	scanf("%d %d",&n,&w);//输入要切割的零件数及矩形板的宽

	printf("\n");

	for(i=1;i<=n;i++){

		scanf("%d %d",&s[i].h,&s[i].w);//输入零件的高及宽

		printf("\n");

		s[i].visited=0;

		if(s[i].w>w)
		{

			printf("the width of the %d th block beyonds the width bound.\n",i);

			return;

		}

	}

/*//将各个零件按高度大小排序*/

    for(i=1;i<=n-1 && flag==1;i++){

		flag=0;

		for(j=1;j<=n-i;j++){

			if(s[j].h<s[j+1].h){

			temp=s[j];

				s[j]=s[j+1];

				s[j+1]=temp;

				flag=1;

			}

		}

	}

     for(i=1;i<=n;i++){

		printf("%d,%d\n",s[i].h,s[i].w);

	}



	h=cut();

    printf("the height of the original block used is %d\n",h);

}



//算法主要切割函数

int cut()

{int i,h;

 for(i=1;i<=n&&s[i].visited==1;i++);//获取高度最大的未切割零件的数据

 h=0;

 while(i<=n){

   s[i].visited=1;//在材料板的新的一个高度范围上切割第一块零件

   h=h+s[i].h;

   height=s[i].h;

   width=w-s[i].w;

   subcut(height,width);

   for(i=1;i<=n&&s[i].visited==1;i++);

   }

 return h;

}



//递归在高度为已切割的第一块零件的高度内的材料板上切割零件

int subcut(int h1,int w1)

{
	int i,h2,w2;

 for(i=1;i<=n;i++)
 {
   if(s[i].visited==0&&s[i].w<=w1&&s[i].h<=h1)
    {
		s[i].visited=1;

        h2=h1-s[i].h;

        w2=w1-s[i].w;

        subcut(s[i].h,w2);

        subcut(h2,w1);
	}
}
return 1;
}