独立任务最优调度问题

一.问题描述

  用2 台处理机A 和B 处理n个作业。设第i 个作业交给机器A 处理时需要时间ai,若由机器B来处理,则需要时间bi。由于各作业的特点和机器的性能关系,很可能对于某些i,有ai>=bi,而对于某些j,j≠i,有aj<bj,既不能将一个作业分开由2 台机器处理,也没有一台机器能同时处理2 个作业。设计一个动态规划算法,使得这2 台机器处理完这n个作业的时间最短(从任何一台机器开工到最后一台机器停工的总时间)。

  input   6              

  2 5 7 10 5 2 

  3 8 4 11 3 4 

  output  15

 

二.问题分析

  下面是错误算法

 1 /*
 2 算法采用二进制枚举,但是这样不对
 3 因为同时有两个处理器 
 4 */
 5 #include <iostream>
 6 #include <cstring>
 7 using namespace std;
 8 
 9 int a[100],b[100];
10 
11 int main()
12 {
13     int i,j,k;
14     int num;
15     while(cin>>num)
16     {
17         int min = 0x7fffffff;//INT_MAX
18         memset(a,0,sizeof(a));
19         memset(b,0,sizeof(b));
20         for(i=0; i<num; i++)
21             cin>>a[i];
22         for(i=0; i<num; i++)
23             cin>>b[i];
24         int s = 1<<num - 1;
25         for(i=0;i<s; i++)//没有等于,想等差数列和 
26         {
27             int sum = 0;
28             for(j=0; j<num; j++)
29             {
30                 if(i&(1<<j))//1的话采用a处理机 
31                     sum += a[j];
32                 else
33                     sum += b[j];  
34             }
35             if(sum<min)
36                 min = sum;             
37         }
38         cout<<min<<endl;
39         
40     }
41     return 0;
42 } 

明天继续写

上一篇:App如何实现就近接入?如何改善调度不准问题?


下一篇:python xrange比range性能更好