divideboard.cpp

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

/*  HELLO.C -- Hello, world */

#include "stdio.h"
#include "conio.h"
#include <stdlib.h>
#include <string.h>
//#include <graphics.h>

#define ERROR 0
#define N  200

typedef struct graph{
     int height;
     int weith;
}a[N];

int H;

int Partition(struct graph a[],int low,int high){
    int pivotkey=a[low].height;
    struct graph t;
    while(low<high){
        while((low<high)&&(a[high].height<=pivotkey)) high--;
        t=a[low];
        a[low]=a[high];
        a[high]=t;
        while((low<high)&&(a[low].height>=pivotkey)) low++;
        t=a[high];
        a[high]=a[low];
        a[low]=t;
    }
    return low;
}

void QickSort(struct graph a[],int low,int high){
    if(low<high){
        int pivotloc=Partition(a,low,high);
        QickSort(a,low,pivotloc-1);
        QickSort(a,pivotloc+1,high);
    }
}



int DivideBoard(struct graph a[],int i,int leftw,int W,int n){
   /*  printf("%d %d %d\t",i,H,leftw);*/
     int j,k;
	 struct graph temp;
     if(i==n){return 1;}
     else
	 {
       if(a[i].weith<=leftw){
         H=H;
         leftw=leftw-a[i].weith;
         i++;
         DivideBoard(a,i,leftw,W,n);
       }
       else
	   {
      /*   H=H+a[i].height;
         leftw=W-a[i].weith;
         i++;
         DivideBoard(a,i,leftw,W,n);   */ 
		   j=i+1;
		   while(j<n)
		   {
			   if(a[j].weith<leftw)
			   {
				   H=H;
				   leftw=leftw-a[j].weith;
                   for(k=j+1;k<n;k++)
				   {
					   a[k-1]=a[k];
					   a[k].weith=0;
					   a[k].height=0;
				   }
				  // DivideBoard(a,j,leftw,W,n);
				   break;
			   }
			   else
			   {
				   j++;
			   }
		   }
           H=H+a[i].height;
		   leftw=W-a[i].weith;
		   i++;
           DivideBoard(a,i+1,leftw,W,n);
	   }
		   //DivideBoard(a,i,leftw,W,n);           
     }
     
}


void main()
{
   FILE *fp;
   char filename[10];
   int n,W;
   int i;
   int Height;
   struct graph a[N];
   while(1){          /*数组h存放木零件的高度，w存放宽度*/
/*  int gdriver;
   int gmode;
   gdriver=DETECT;
   initgraph(&gdriver, &gmode, "");  //图形模式初始化*/

   printf("please input filename:");
   /*getch();*/
   scanf("%s",filename);
   printf("\n");

   if((fp=fopen(filename,"r"))==NULL)
   {
      printf("cann't open file\n");
      getch();
      exit(0);
   }
   fscanf(fp,"%d",&n);
   fscanf(fp,"%d",&W);
   printf("%d,%d\n",n,W);

   for(i=0;i<n;i++)
   {
      fscanf(fp,"%d",&a[i].height);
      fscanf(fp,"%d",&a[i].weith);
   }
   fclose(fp);              /*从文件读取相关数据*/

   for(i=0;i<n;i++){
      printf("%d %d\t",a[i].height,a[i].weith);
   }
   printf("\n");

   QickSort(a,0,n-1);           /*按木零件高度从大到小排序*/

   for(i=0;i<n;i++){
      printf("%d %d\t",a[i].height,a[i].weith);

   }
   printf("\n");


 /*  line(200,450,200,10);
   line(200+W,450,200+W,10);
   line(200,450,200+W,450);     //画出宽为W，高不受限制的矩形板*/
   H=a[0].height;
   DivideBoard(a,1,W-a[0].weith,W,n);

   printf("the Height is:%d\n",H);
   getch();
   }
}