算法__贪心__活动安排问题

• 考虑将一系列活动安排在科学会堂。假设有n个活动，每个活动需要花费一个单位时间。如果在时间T[i]或T[i]之前开始，则活动i将提供P[i]元的利润，其中T[i]是任意的数字。如果一个活动不是在T[i]或T[i]之前开始的，那么在安排过程中它根本不会带来任何利润。如果所有事件都可以在0时刻开始。
• 输入：n个活动的T[i]和P[i]
• 输出：活动安排顺序和获得的利润。
• 解：

  #include<stdio.h>
  typedef struct
  {
      int T;
      int P;
      int flag;
  }LNode;
  //倒着安排活动使损失最小，如果刚好有活动截止就安排它，不然安排其他受益最大的活动，若都过期了就安排损失最小的活动。 
  int main()
  {
      LNode A[20]; 
      int X[20];
      int n,i,j,k;
      int sum=0;
      scanf("%d",&n);
      for(i=1;i<=n;i++)
      {
          scanf("%d %d",&A[i].T,&A[i].P);
          A[i].flag=0;
      }
      for(i=n;i>=1;i--)
      {
          int isover=1,isok=0; 
          int mini,maxi,min,max;
          max=-1,min=10000;
          for(j=1;j<=n;j++)
          {
              if(A[j].flag==0&&A[j].T==i)//如果刚好有个活动截止，就直接安排 
              {
                  X[i]=j;
                  sum+=A[j].P;
                  A[j].flag=1;
                  isover=0;
                  break;
              }
              if(A[j].flag==0&&A[j].T<i)//过期的活动
              {
                  if(A[j].P<min)
                  {
                      mini=j;
                      min=A[j].P;
                  }
              }
              if(A[j].flag==0&&A[j].T>=i)//没过期的活动 
              {
                  if(A[j].P>max)
                  {
                      maxi=j;
                      max=A[j].P;
                      isok=1;
                  }
              }
          }
          if(isover==0)
              continue;
          if(isok==1)
          {
              X[i]=maxi;
              sum+=A[maxi].P;
              A[maxi].flag=1;
          }
          else
          {
              X[i]=mini;
              A[mini].flag=1;
          }    
      }
      printf("%d: ",sum);    
      for(i=1;i<=n;i++)
      {
          printf("%d ",X[i]);
      }
      return 0;
  }

   

算法__贪心__活动安排问题

原文：https://www.cnblogs.com/hiyori/p/14901073.html