最小重量机器问题源码

最小重量机器问题源码（分支限界，回溯法）

#include “fstream.h“   
#include “iostream.h“   
struct nodetype  
{   
      int peer;   
      struct nodetype *parent;   
      int position;   
      double cw;   
      double cv;   
      double r;    
};   
struct nodetype *queues[100000000];   
  
void insert（struct nodetype *x int oldlast） //x是要插入的数
{ 
	//oldlast是目前堆的元素数目                                                
     int last = oldlast+1;
     queues[last]=x;
     int i=last;                                                       
     while（（i > 1）&&（queues[i]->r < queues[i/2]->r））
	 {
		 struct nodetype *temp;
         temp=queues[i];   
         queues[i]=queues[i/2];
         queues[i/2]=temp;
         i = i/2; 
	 } 
}						                                                           
struct nodetype * deletemin（int laststruct nodetype *a[]） 
{      //返回堆的第一个元素（即最小元素）     
	 struct nodetype *temp;
     temp=a[1]; 
     a[1]=a[last]; 
     last --;                                                        
     int i = 1;   
	 int j=0;                                                        
     while（i <= last/2）                                               
	{  
		 if（（a[2*i]->r < a[2*i+1]->r）||（2*i == last）） 
         j = 2*i; 
         else
			  j=2*i+1;                                                    
		 if（a[i]->r > a[j]->r） 
		  {                      
            struct nodetype *temp;   
            temp=a[i];   
            a[i]=a[j];   
            a[j]=temp;
            i = j;                                                  
          }                                                           
           else 
			   return（temp）;                                          
       }                                                               
       return（temp）;                                                   
   }                                                                      
  void main（）  /////////////////////////////////小根堆///////////////////////////////   
   {   
       ifstream fin（“input.txt“）;   
       ofstream fout（“output.txt“）;   
       int nmc;   
       fin>>n;fin>>m;fin>>c;   
       double **w=new  double*[n+1];   
       double **cc=new double*[n+1];   
       for（int i=1;i<=n;i++）
	   {   
          w[i]=new double[m+1];   
          cc[i]=new double[m+1];   
       }   
       for（i=1;i<=n;i++）   
           for（int j=1;j<=m;j++）   
            fin>>cc[i][j];   
       for（i=1;i<=n;i++）   
            for（int j=1;j<=m;j++）   
            fin>>w[i][j];   
        double *cmin=new double[n+1];   
        double *wmin=new double[n+1];   
        for（i=1;i<=n;i++） 
		{   
         cmin[i]=cc[i][1];   
         wmin[i]=w[i][1];   
		   for（int j=2;j<=m;j++） 
		   {   
			if（cmin[i]>cc[i][j]） cmin[i]=cc[i][j];   
            if（wmin[i]>w[i][j]） wmin[i]=w[i][j];   
		   }   
		}   
    double *rc=new double[n+1];//剩余部件最小价格和   
    double *rw=new double[n

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件         14  2011-06-21 08:41  output.txt

     文件         42  2011-06-21 08:41  input.txt

     文件       4577  2011-06-21 08:39  分支限界.cpp

     文件       1964  2011-06-21 08:28  回溯法.cpp

----------- ---------  ---------- -----  ----

                 6597                    4