实验一.c

这是一个分治解决的零件切割问题:给定一块宽度为W的矩形板

#include <graphics.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int h[200];
int w[200];
int kuaishu;
int n;
int W;
int h1=0;
int h2=0;
int x=200;
int y=450;
int flag=0;

main()
{
	FILE *fp;
	int gdriver;
	int gmode;
	int buf1;
	int buf2;
	int i=0;
	int j;
	int t;
	gdriver=DETECT;
	initgraph(&gdriver, &gmode, "F:\\vc\\turbo2");

	for(i=0;i<200;++i)
		h[i]=0;
	for(i=0;i<200;++i)
		w[i]=0;

	if((fp = fopen("F:\\vc\\turbo2\\110.txt","r")) == NULL)
		return -1;

	fscanf(fp,"%d",&n);
	fscanf(fp,"%d",&W);
	for (i=0;i<n;i++)
	{
		fscanf(fp,"%d\n",&h[i]);
		fscanf(fp,"%d\n",&w[i]);
	}
	fclose(fp);

	line(200,450,200,10);
	line(200+W,450,200+W,10);
	line(200,450,200+W,450);
	
	for(j=0;j<n;j++)
	{
		for(i=0;i<n-j;i++)
		{
            if(h[i]<h[i+1])
			{
				t=h[i];
				h[i]=h[i+1];
				h[i+1]=t;
				t=w[i];
				w[i]=w[i+1];
				w[i+1]=t;
				
			}
		}
	}
	kuaishu=n;
	
	while (kuaishu>0)
	{
		
		h1=h1+h[0];
		h2=h[0];
		buf1=h[0]; buf2=w[0];
		
		rectangle(x,y-buf1,x+buf2,y);
		
		x=x+buf2;
		for(i=1;i<=kuaishu;++i) 
		{
			h[i-1]=h[i]; 
			w[i-1]=w[i];
		}
		kuaishu=kuaishu-1;
		incise(buf2,buf1);
		x=200;y=450-h1;
	}
	printf("\t\t\tThe best solution is:%d\n",h1);
	getch();
	return 0;
}


int incise(int left,int high)
{
	int wi=W-left;
	int i=0;
	int j;
	int buf1,buf2;
	
	while(i<kuaishu)
	{
		if (h[i]<=high && w[i]<=wi)
		{     
			buf1=h[i];
			buf2=w[i];
			rectangle(x,y-buf1,x+buf2,y);
			for(j=i+1;j<=kuaishu;++j) 
			{
				h[j-1]=h[j]; 
				w[j-1]=w[j];
			} 
			kuaishu=kuaishu-1;
			flag++;
			x=x+buf2;
			incise(left+buf2,buf1);
			x=left+200;y=450-h1+h2-buf1;
			incise(left,high-buf1);
			return 0;
		}
		else i++;
	}
	return 0;
}