零件切割问题.cpp

给定一块宽度为W的矩形板

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

#include<stdio.h>
#include <iostream>
using namespace std;
#define MAX 1000

//定义零件结构
typedef struct block{
	int w;//宽
	int h;//高
	int visited;//是否已经被切割
}ss;

ss s[MAX];

int h=0,n,height,width,w;
int insert();
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 %dth block beyonds the width bound.\n");
			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].w,s[i].h);
	}

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

//算法主要切割函数
int cut()
{int i;
 for(i=1;i<=n&&s[i].visited==1;i++);//获取高度最大的未切割零件的数据
 height=h;
 if(i<=n){
   s[i].visited=1;//在材料板的新的一个高度范围上切割第一块零件
   h=h+s[i].h;
   height=s[i].h;
   width=w-s[i].w;
   subcut(height,width);
   insert();
   }
 return h;
}

//递归在高度为已切割的第一块零件的高度内的材料板上切割零件
int subcut(int h1,int w1)
{int i,h2,w2;
 for(i=1;i<=n&&s[i].visited==1;i++);
  if(i<=n){
    if(w1<=0||h1<=0) return 1;
    if(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);}
   }
}