johnson算法

问题就是2台机器，n件任务，必须先在S1上做，再在S2上做。任务之间先做后做任意。求最早的完工时间。

这是一个经典问题：2台机器的情况下有多项式算法（Johnson算法），3台或以上的机器是NP-hard的。思想就是贪心，时间复杂度是O(nlogn) 。

Johnson算法

(1)    把作业按工序加工时间分成两个子集，第一个集合中在S1上做的时间比在S2上少，其它的作业放到第二个集合。先完成第一个集合里面的作业，再完成第二个集合里的作业。

(2)    对于第一个集合，其中的作业顺序是按在S1上的时间的不减排列；对于第二个集合，其中的作业顺序是按在S2上的时间的不增排列。

怎么证呢？

   1: #include <iostream>

   2: #include <cstdio>

   3: #include <algorithm>

   4: using namespace std;

   5: const int maxn = 10005;

   6: struct node{

   7:     int x,y;

   8: }a[maxn],b[maxn],c[maxn];

   9: bool cmp1(const node &p, const node &q) 

  10: {

  11:     return p.x < q.x;

  12: }

  13: bool cmp2(const node &p, const node &q)

  14: {

  15:     return p.y > q.y;

  16: }

  17: int n;

  18: int s1sum[maxn];

  19: int sum;

  20: int main()

  21: {

  22:     //freopen("test.txt","r",stdin);

  23:     while(scanf("%d",&n) && n)

  24:     {

  25:         for(int i=0;i<n;++i)

  26:             scanf("%d%d",&a[i].x,&a[i].y);

  27:         int len1 = 0, len2 = 0;

  28:         for(int i=0;i<n;++i)

  29:         {

  30:             if(a[i].x < a[i].y)

  31:             {

  32:                 b[len1].x = a[i].x;           //子集1 x<y

  33:                 b[len1++].y = a[i].y;

  34:             }

  35:             else

  36:             {

  37:                 c[len2].x = a[i].x;           //子集2

  38:                 c[len2++].y = a[i].y;

  39:             }

  40:         }

  41:         sort(b,b+len1,cmp1);                  //子集1作业顺序：x不减

  42:         sort(c,c+len2,cmp2);                  //子集2作业顺序：y不增

  43:         for(int i = len1;i<len1+len2;++i)

  44:             b[i] = c[i-len1];

  45:         s1sum[0] = 0;

  46:         for(int i=0;i<n;++i)

  47:             s1sum[i+1] = s1sum[i]+b[i].x;

  48:         sum = 0;

  49:         for(int i=0;i<n;++i)

  50:         {

  51:             if(sum<s1sum[i+1]) sum = s1sum[i+1]+b[i].y;

  52:             else sum+=b[i].y;

  53:         }

  54:         printf("%d\n",sum);

  55:     }

  56: }

本站声明:网站内容来源于网络,如有侵权,请联系我们https://www.qiquanji.com,我们将及时处理。

微信扫码关注

更新实时通知