newplan

阿基米德在洗澡時發現浮力原理,高興得來不及穿㆖褲子,跑到街㆖大喊:Eureka(我找到了)。
posts - 39, comments - 26, trackbacks - 0, articles - 4
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

算法 实验 4

Posted on 2008-06-10 21:47 山泉弯延 阅读(255) 评论(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(
250250200)));
     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();

}


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理