main.c

MPI 并行编程 一维0/1口袋问题 动态规划 求优化解

#include <stdio.h>
#include <stdlib.h>
#include "mpi.h"
#include <malloc.h> 

int random(int seed,int max);
void makeItemlist(int size,int *w,int *v,int capacity);
void printitems(int *weight,int *value,int num_items);
void printsolution(int *solution,int *value,int *weight,int num_items);
int ** getmatrix(int count_items,int capacity);
void freematrix(int ** matrix,int capacity);
void getsolution(int ** table,int n,int m,int *solution,int *weight);
//-------------------------------------------------------------------
int main(int argc, char *argv[])
{
  MPI_Init(&argc,&argv);
  int NumProc,myrank,dest,src,namelen,bagsize;

  char processor_name[MPI_MAX_PROCESSOR_NAME];
  MPI_Request Srequest,*Rrequest;
  MPI_Status  Sstatus,*Rstatus;
  
  MPI_Comm_rank( MPI_COMM_WORLD, &myrank);
  MPI_Comm_size(MPI_COMM_WORLD,&NumProc);
  MPI_Get_processor_name(processor_name,&namelen);
  bagsize=NumProc;
  int count_items;
  
 if(myrank==0)
  {
     //printf("enter the count of items\n");
     scanf("%d",&count_items);
  }
  /* count_items=6;*/
  
  MPI_Bcast(&count_items,1,MPI_INT,0,MPI_COMM_WORLD);
  int *value;int*weight;int *pro;int *colum;
  value=  (int*)malloc(count_items*sizeof(int));
  weight= (int*)malloc(count_items*sizeof(int));
  colum=  (int*)malloc(count_items*sizeof(int));
  pro=    (int*)malloc(count_items*sizeof(int)); 
  Rrequest=(MPI_Request*)malloc(count_items*sizeof(MPI_Request));
  Rstatus=(MPI_Status*)malloc(count_items*sizeof(MPI_Status));
  /*
  weight[0]=2;value[0]=1;
  weight[1]=3;value[1]=5;
  weight[2]=6;value[2]=7;
  weight[3]=8;value[3]=10;
  weight[4]=9;value[4]=11;
  weight[5]=10;value[5]=12;*/
  //------------------------make item list----------------------------
  if(myrank==0)
  {
      makeItemlist(count_items,weight,value,bagsize);
      //printitems(weight,value,count_items);
  }
  //------------------------------------------------------------------
  MPI_Bcast(weight,count_items,MPI_INT,0,MPI_COMM_WORLD);//broadcast itemlist
  MPI_Bcast(value ,count_items,MPI_INT,0,MPI_COMM_WORLD);//broadcast itemlist
  pro[0]=0;
  int i;
  for(i=1;i<count_items;i++)
    pro[i]=-1;
  int capacity=myrank+1;
  if(capacity>=weight[0])
    colum[0]=value[0];
  else
    colum[0]=0;
  dest=myrank+weight[1];
  short sent;
  sent=0;
  if(dest<=bagsize-1)
  {
    MPI_Isend(&colum[0],1,MPI_INT,dest,1,MPI_COMM_WORLD,&Srequest);
    sent=1;
  }
  for(i=1;i<count_items;i++)
    MPI_Irecv(&pro[i],1,MPI_INT,MPI_ANY_SOURCE,i,MPI_COMM_WORLD,&Rrequest[i]);
    
  for(i=1;i<count_items;i++)
  {
     if(capacity>=weight[i])
     {
          if(capacity==weight[i])
            pro[i]=0;
          if(pro[i]==-1)
            MPI_Wait(&Rrequest[i],&Rstatus[i]);   
          if(pro[i]+value[i]>colum[i-1])
            colum[i]=pro[i]+value[i];
          else
            colum[i]=colum[i-1];
     }
     else
       colum[i]=colum[i-1];
     if(sent==1)
     {
       MPI_Wait(&Srequest,&Sstatus);
       sent=0;
     }
     dest=myrank+weight[i+1];
     if(dest<=bagsize-1)
     {
       MPI_Isend(&colum[i],1,MPI_INT,dest,i+1,MPI_COMM_WORLD,&Srequest);
       sent=1;
     }
  }
//------------------------cancel communication which havent involved in computation---------------
  int flag;
  for(i=1;i<count_items;i++)
  {
    MPI_Test(&Rrequest[i],&flag,&Rstatus[i]);
    if(flag==0)
      MPI_Cancel(&Rrequest[i]);
    while(flag!=0)
      MPI_Test_cancelled(&Rstatus[i],&flag);
  }
   if(myrank==bagsize-1)
      printf("Highest index value(optimal):%d\n",colum[count_items-1]);
//-----------------collect vector-----------------------------  
  
  int *solution=NULL;
  int **table=NULL;
  if(myrank==0)
  {
    free(Rrequest);
    free(Rstatus);
    Rrequest=(MPI_Request*)malloc((bagsize-1)*sizeof(MPI_Request));
    Rstatus=(MPI_Status*)malloc((bagsize-1)*sizeof(MPI_Status));
    
    solution=  (int*)malloc(count_items*sizeof(int));
    
    table=getmatrix(count_items,bagsize);
    for(i=1;i<=count_items;i++)
        table[1][i]=colum[i-1];
    for(i=2;i<=bagsize;i++)
    {
          MPI_Irecv((table[i]+1),count_items,MPI_INT,i-1,88,MPI_COMM_WORLD,&Rrequest[i-2]);
    }
    MPI_Waitall(bagsize-1,Rrequest,Rstatus);
  }
  else
    MPI_Send(colum,count_items,MPI_INT,0,88,MPI_COMM_WORLD);
  
  
  if(myrank==0)
  {
    getsolution(table,count_items,bagsize,solution,weight);
    printf("Capacity of knapsack:%d\n",bagsize);
    printf("items: ");
    printitems(weight,value,count_items);
    printsolution(solution,value,weight,count_items);
    freematrix(table,bagsize);
    free(solution);
  }
  //if(myrank==bagsize-1)
    //  printf("optimal value:%d\n",colum[count_items-1]);
  
  free(value);
  free(weight);
  free(colum);
  free(pro);
  free(Rrequest);
  free(Rstatus);
  MPI_Finalize();
  return 0;
}
//-----------------------------------------------------------

//-----------------------------------------------------------
int random(int seed,int max)
{
    srand(seed);
    seed=rand()%max;
    return seed;
}
//-----------------------------------------------------------
void makeItemlist(int size,int *w,int *v,int capacity)
{
    capacity=capacity/2;
    
    int i=0;
    for(;i<size;i++)
    {
       w[i]=random((~i)<<2,capacity)+1;
       v[i]=random((~i)<<2,100);
    }
}
//-----------------------------------------------------------
void printsolution(int *solution,int *value,int *weight,int num_items)
{
     int i=0;int optimal=0;int w=0;
     printf("Selected items:");
     for(;i<num_items;i++)
     {
         if(solution[i]==1)
         {
           printf("#%d ",i);
           optimal=optimal+value[i];
           w=w+weight[i];
         }  
     }
     printf("\nOptimal value:%d\n",optimal);
     printf("Total weight:%d\n",w);
}
//-----------------------------------------------------------
void printitems(int *weight,int *value,int num_items)
{
     int i=0;
     for(;i<num_items;i++)
     {
         printf("{ID:%d,W:%d,V:%d} ",i,weight[i],value[i]);
     }
     printf("\n");
}
//-----------------------------------------------------------
int ** getmatrix(int count_items,int capacity)
{
    count_items=count_items+1;
    capacity=capacity+1;
    int row=0,line=0;
    int **matrix;
    matrix= (int**)malloc(capacity*sizeof(int*));
    for(row=0;row<capacity;row++)
    {
        matrix[row]=(int*)malloc(count_items*sizeof(int));
    }
    for(row=0;row<count_items;row++)
       matrix[0][row]=0;
    for(line=1;line<capacity;line++)
       matrix[line][0]=0;
    return matrix;
}
//---------------------------------------------------------
void freematrix(int ** matrix,int capacity)
{
    capacity++;
    int row=0;
    for(row=0;row<capacity;row++)
    {
        free(matrix[row]);
    }
    free(matrix);
}
//---------------------------------------------------------
void getsolution(int ** table,int n,int m,int *solution,int *weight)
{
     int index=m;
     int i;
     for(i=n;i>=1;i--)
     {
             if(table[index][i]!=table[index][i-1])
             {
                  solution[i-1]=1;
                  index=index-weight[i-1];
             }
             else
                  solution[i-1]=0;
     }
}