Posted on 2008-06-10 21:47
山泉弯延 阅读(344)
评论(0) 编辑 收藏 引用
/*
6.10
*/
/*==========INCLUDES BEGIN===============*/
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <algorithm>
#include <QApplication>
#include <QWidget>
#include <QPainter>
#include <Qt>
/*==========INCLUDE END==================*/
/*==========MACROS BEGIN=================*/
#define MAX 100000000
#define BUFFER 300
#define INPUTFILE "./50.txt"
/*==========MACROS END==================*/
/*==========STD DECLRARS BEGIN===========*/
using std::cout;
using std::cin;
using std::endl;
using std::ios;
using std::ifstream;
using std::sort;
using std::max;
/*==========STD DECLARS END===============*/
/*============STRUCTS BRGIN===============*/
struct Space {
int x;
int y;
int w;
int h;
bool v;//IF VISITED THEN V =TURE ELSE FLASE
};
struct Gadget
{
int x;
int y;
int w;
int h;
};
/*=============STRUCT END=================*/
/*===========GADGET CUT BEGIN=============*/
Gadget result[BUFFER];
Gadget g[BUFFER];
int bestH;
Space space[BUFFER];
int spaceNum ;
int W;
int N;
int H;
ifstream Fin;
int deep;
clock_t start;
clock_t end;
/*-------------FRIENDS METHOD--------------------*/
bool mycmpG(Gadget t1,Gadget t2){return t1.h>t2.h;}
/*-------------FRIENDS METHOD--------------------*/
bool mycompS(Space t1,Space t2){return t1.y<t2.y;}
/*-------------CONSTRUCT METHOD------------------*/
void init()
{
Fin.open(INPUTFILE,ios::in);
Fin>>N;
Fin>>W;
for(int i=0;i<N;i++)
Fin>>g[i].h>>g[i].w;
sort(g,g+N,mycmpG);
space[0].x=space[0].y=0;
space[0].h=MAX;
space[0].w=W;
for(int i=0;i<N;i++)
space[0].v=false;
H=0;
deep=0;
bestH = MAX;
spaceNum = 1;
}
/*-------------CUT METHOD------------------*/
bool canBeCut(Gadget &g,int i,int &TaddSpace)
{
int addSpace = 0;
if((space[i].h>=g.h)&&(space[i].w>=g.w)){
if(space[i].w>g.w){
space[spaceNum].x = space[i].x+g.w;
space[spaceNum].y = space[i].y;
space[spaceNum].h = g.h;
space[spaceNum].w = space[i].w - g.w;
addSpace++;
}
if(space[i].h>g.h){
space[spaceNum+1].x = space[i].x;
space[spaceNum+1].y = space[i].y+g.h;
if(space[i].h==MAX)
space[spaceNum+1].h = MAX;
else
space[spaceNum+1].h = space[i].h - g.h;
space[spaceNum+1].w = space[i].w;
addSpace++;
}
g.x = space[i].x;
g.y = space[i].y;
H = max(H,g.y+g.h);
spaceNum += addSpace;
TaddSpace = addSpace;
return true;
}
return false;
}
/*-------------THE MAIN METHOD--------------------*/
void backTrack(int which)
{ // if(deep==100000)return;
// else deep++;
sort(space,space+spaceNum,mycompS);
Space temp[BUFFER];
for(int i=0;i<spaceNum;i++)
temp[i] = space[i];
if(which==N)
{
if(H<bestH)
{ bestH = H;
for(int i = 0;i<N;i++)
result[i]=g[i];
}
return;
}
int addSpace;
int Num=spaceNum;
for(int i=0;i<Num;i++)
if(space[i].v == false)
{
int tempH=H;
if(canBeCut(g[which],i,addSpace))
{
if(H>bestH)//剪枝
{
H = tempH;
spaceNum -= addSpace;
continue;
}
space[i].v = true;
backTrack(which+1);
spaceNum-=addSpace;
space[i].v = false;
H = tempH;
for(int k=0;k<spaceNum;k++)
space[k] = temp[k];
}
}
}
/*===========GADGET CUT END=============*/
/*========NEWBOX CLASS BEGIN============*/
class NEWBOX:public QWidget
{
public:
NEWBOX(QWidget *parent=0);
protected:
void paintEvent(QPaintEvent *event);
private:
};
/*NEWBOX METHOD*/
/*-----------------------------------*/
NEWBOX::NEWBOX(QWidget *parent):QWidget(parent)
{
setFixedSize(W*15,30*15);
char temp[5];
sprintf(temp,"%d",bestH);
char title[40]="H:";
strcat(title,temp);
char temp2[20]=" Spend TIME:";
char temp3[5];
sprintf(temp3,"%f",(double)(end-start)/CLOCKS_PER_SEC);
strcat(temp2,temp3);
strcat(title,temp2);
setWindowTitle(title);
setPalette(QPalette(QColor(250, 250, 200)));
setAutoFillBackground(true);
}
/*-----------------------------------*/
void NEWBOX::paintEvent(QPaintEvent *)
{ QPainter painter(this);
painter.setPen(Qt::SolidLine);
painter.setBrush(Qt::blue);
painter.translate(0,0);
for(int i=0;i<=N;i++)
painter.drawRect(result[i].x*15,30*15-result[i].y*15,
result[i].w*15,-result[i].h*15);
}
/*=========NEWBOX CLASS END=============*/
int main(int argc, char *argv[])
{ QApplication app(argc, argv);
init();
start=clock();
backTrack(0);
end= clock();//TIME END HERE
NEWBOX newb;
newb.show();
return app.exec();
}