test4.cpp

这是一个运用回溯法解决关于"最佳切割问题"的程序."最佳切割问题"是指给定一个宽已知的木板,有众多零件,如何拼接才能最小程度的耗费木板,也就是说使所需木板的高度最小.这一问题在许多实际应用中需要考虑到

#include <math.h>
#include <stdio.h>
#include "stdlib.h"
#include <time.h>
#include "string.h"
#include "draw.h"
FILE *fpout=stdout;
FILE *fpin=stdin;
#define		MAX			1111111
long		MAXSEARCH =1000000;     //remark the largest depth 
int		totalArea = 0;
int		search = 0;
int		totalHeight = 0;
int		N = 0;
int		dCounter = 0;
int		bNumber = 0;
int		Wide = 0;
int		W[1000], H[1000];
int		bPos[1000][2];
int		bCut[1000];
int		divided[1000][3];
int		bestHeight = MAX;
int		bestPos[1000][4];

void mergeSpace( int dividedNumber )     
{
	if(dCounter<=1) return;
	if ( dividedNumber == 0 ) {
		divided[dividedNumber+1][0] = divided[dividedNumber][0];
		divided[dividedNumber+1][2] += divided[dividedNumber][2];
	} else if ( dividedNumber == dCounter-1 ) {
		divided[dividedNumber-1][2] += divided[dividedNumber][2];
	} else if ( divided[dividedNumber-1][1] > divided[dividedNumber+1][1] ) {
		divided[dividedNumber+1][0] = divided[dividedNumber][0];
		divided[dividedNumber+1][2] += divided[dividedNumber][2];
	} else if ( divided[dividedNumber-1][1] < divided[dividedNumber+1][1] ) {
		divided[dividedNumber-1][2] += divided[dividedNumber][2];
	} else if ( divided[dividedNumber-1][1] == divided[dividedNumber+1][1] ) {
		divided[dividedNumber-1][2] += divided[dividedNumber][2];
		divided[dividedNumber-1][2] += divided[dividedNumber+1][2];
		for ( int i = dividedNumber; i < dCounter-1; i++ ) {
			divided[i][0] = divided[i+1][0];
			divided[i][1] = divided[i+1][1];
			divided[i][2] = divided[i+1][2];
		}
		dCounter--;
	}
	for ( int i = dividedNumber; i < dCounter-1; i++ ) {
		divided[i][0] = divided[i+1][0];
		divided[i][1] = divided[i+1][1];
		divided[i][2] = divided[i+1][2];
	}
	dCounter--;
	return;
}
void divideSpace( int dividedNumber, int height, int weight )
{  
	if ( divided[dividedNumber][2] == weight ) {
		divided[dividedNumber][1] += height;
		return;
	}
	for ( int i = dCounter; i > dividedNumber; i-- ) {
		divided[i][0] = divided[i-1][0];
		divided[i][1] = divided[i-1][1];
		divided[i][2] = divided[i-1][2];
	}
	dCounter++;
	divided[dividedNumber+1][0] = divided[dividedNumber][0] + weight;
	divided[dividedNumber+1][1] = divided[dividedNumber][1];
	divided[dividedNumber+1][2] = divided[dividedNumber][2] - weight;
	divided[dividedNumber][1] += height;
	divided[dividedNumber][2] = weight;
}
int Update( void )
{
	for ( int i = 0; i < N; i++ ) {
		bestPos[i][0] = bPos[i][0];
		bestPos[i][1] = bPos[i][1];
	

	}
	bestHeight = totalHeight;
	return 0;
}

void print(){
    int color;
	if (fpout==0) {
		printf("error open \n");
	    return ;

	}
		fprintf(fpout,"%d %d\n",N,Wide);
	for ( int i = 0; i < N; i++ ) {

		int t1,t2;
		 t1=bestPos[i][0];
		 t2=bestPos[i][1];
		bestPos[i][0] = 100+bestPos[i][0];
		bestPos[i][1] = 450-bestPos[i][1]-H[i];
		bestPos[i][2] = 100+t1+W[i];
		bestPos[i][3] =450- t2;
        color=rand()%16;
		  if(color==0) color++;
		  ezdSetColor(ezdWhite+color);
		  delayWindow(0.1);
		  ezdDrawRectangle(bestPos[i][0],bestPos[i][1],bestPos[i][2],bestPos[i][3]);
		//fprintf(fpout,"%d %d %d %d\n",bestPos[i][0],bestPos[i][1],bestPos[i][2],bestPos[i][3]);
	}
}

int Backtrack( void )
{
	if ( search++ > MAXSEARCH ) {
		return 0;
	}

	if ( bNumber == N ) {
		if ( totalHeight < bestHeight ) {
			Update();
		}
		return 0;
	}
	if ( bNumber >= N ) return 0;

	int		tmpH;
	if ( totalHeight > bestHeight ) return 0;

	int		count = 0, pHeight = 0, tmp[300][3];
	int		i, j, sMin, sIndex;
	sMin = MAX; sIndex = -1;
	for ( i = 0; i < dCounter; i++ ) {
		if ( divided[i][1] < sMin ) {//the index for the lowest height
			sIndex = i;
			sMin = divided[i][1];
		}
	}
	tmpH = (int)(totalArea/Wide);
	if ( divided[sIndex][1]+tmpH > bestHeight ) return 0;
	int		flag = 0, bIndex = -1;
	for ( i = 0; i < N; i++ ) {
		if ( W[i] <= divided[sIndex][2] && bCut[i] == 0 ) {
			bIndex = i;
			bPos[bIndex][0] = divided[sIndex][0]; bPos[bIndex][1] = divided[sIndex][1];
			bCut[bIndex] = 1;
			totalArea-=W[i]*H[i];
			if ( divided[sIndex][1]+H[bIndex] > totalHeight ) {
				pHeight = totalHeight;
				totalHeight = divided[sIndex][1]+H[bIndex];
				flag = 1;
			}
			bNumber++;
			count = dCounter;
			for( j = 0; j < dCounter; j++ ) {
				tmp[j][0] = divided[j][0];
				tmp[j][1] = divided[j][1];
				tmp[j][2] = divided[j][2];
			}
		
			divideSpace( sIndex, H[bIndex], W[bIndex] );
			Backtrack();
		
			//recover
			totalArea+=W[i]*H[i];
			for( j = 0; j < count; j++) {
				divided[j][0] = tmp[j][0];
				divided[j][1] = tmp[j][1];
				divided[j][2] = tmp[j][2];
			}
			dCounter = count;
			bCut[bIndex] = 0;
			if ( flag ) {
				totalHeight = pHeight;
				flag = 0;
			}
			bNumber--;
		}
	}
	if ( bIndex == -1 ) {   //union the free space for  the  larger block
		mergeSpace( sIndex );
		Backtrack();
	} else return 0;
	return 0;
}

void copyright(){
	fprintf(fpout,"Usage:experiment4 sourcefile\n");
	fprintf(fpout,"sourcefile denotes the name of the input file\n");

}


int main(int argc,char *argv[])
{
  	int	t = clock();int flag=0;
	time_t temp;
	char str[30]="ans_";
	if(argc==1){
	    copyright();
		exit(0);
	}
  
	if(argc==2){
       strcat(str,argv[1]);
 	   fpout=fopen(str,"w");
  	   fpin=fopen(argv[1], "r");
	}

	
    if (fpin==0) {
		printf("open file %s error\n",argv+1);
		return 0;
    }
    fscanf(fpin,"%d %d",&N,&Wide);
	for ( int i = 0; i < N; i++ ) {
	fscanf(fpin,"%d %d",&H[i],&W[i]);
		totalArea += H[i]*W[i];
	}

	divided[0][0] = 0; divided[0][1] = 0;
	divided[0][2] = Wide; dCounter = 1;
	 openWindow();
	 if(Wide<80) {
		 ezdSetOrigin(0,+460,ezdAtPoint);
		 ezdSetViewport(150,-100);
    }
	else if(Wide<120) {
		ezdSetOrigin(0,+500,ezdAtPoint);
		ezdSetViewport(450,-400);
	}
	else {
		ezdSetOrigin(0,+700,ezdAtPoint);
		ezdSetViewport(650,-600);
	}
	 ezdSetColor(ezdBlack);
	 ezdDrawLine(100,200,100,450);
    ezdDrawLine(100+Wide,200,100+Wide,450);
	ezdDrawLine(100,450,100+Wide,450);
	
	
	
	srand((unsigned)time(&temp));
	Backtrack(); //call Backtrack
	printf("time:%d\n",clock()-t);
	print();
	fprintf(stdout,"TotolHeight: %d\n", bestHeight);
	fprintf(fpout,"%d\n", bestHeight);
	fclose(fpout);
	fclose(fpin);
	delayWindow(5);	
	closeWindow();
	return 0;
}