11089 多机最佳调度

时间限制:13000MS  内存限制:65535K
提交次数:0 通过次数:0

题型: 编程题   语言: 无限制

Description

假设有n个任务（n<=100），m台机器（m<=50），任务可以由任何一个机器完成，完成任务i需要的时间为ti，
请设计两种算法（一种采用贪心算法，另一种采用回溯算法），找出完成这n个任务的最佳调度，使得最早时间完成全部任务。

这里采用两种算法来求解：
1）贪心算法可以得到近似的最早完成时间，算法思想在书上4.7节。
2）回溯算法搜索m叉树（除叶节点外每个节点m个儿子），寻找最早的完成时间。

输入格式

输入两行，第一行为n和m，中间空格相连（其中n表示任务的数量，m表示机器的数量），（n<=100, m<=50）。
第二行的n个数是任务i的处理时间ti。

输出格式

输出两行，第一行为采用贪心算法算出的最早完成时间，第二行为采用回溯算法搜索出的最早完成时间。

输入样例

7 3
2 14 4 16 6 5 3

另一个输入示例：
14 3 
10 10 10 10 10 7 7 7 7 7 5 5 5 5

输出样例

17
17

另一个输出示例：
37
35

提示

第（1）个贪心算法按书上思想去实现。
第（2）个就是在m叉树上深度优先搜寻最优解的过程。
//t数组为初始的任务处理时间；
//len2数组为第二种回溯算法在搜索过程中已探察过任务的完成时间和；
//x数组用来保存探察过的任务编号。
void backtrack (int dep)
{
    if (dep == n) //叶子，或者if (dep>n)，看首次调用backtrack参数是0还是1
    {
        ……
        return;
    }

    for(int i = 0; i < m; i++)
    {
        len2[i] += t[dep];
        x[dep] = i+1;

        if(len2[i] < best)
        {
        	    backtrack(dep+1);
        }

        len2[i] -= t[dep];
    }
}

 

#include <iostream>

#include <stdio.h>

#include <algorithm>

using namespace std;

int n,m;

int t[1000]={0};

int a[100]={0};

int aa[100]={0};

int res=100000;

int greedy(){

    sort(t,t+n);

    if(n<m){

        int res=t[0];

        for(int i=1;i<m;i++) //取最大值 作为工作时间

            if(res < t[i])

            res = t[i];

        return res;

    }else{

 

     for(int i=0,j=n-1;j>=0;i++,j--)

    {

        if(i<m){

            a[i]=t[j];  // 取最大的工作 分配给M个机器

        }else{

 

            int res=a[0];

            int ii=0;

        for(int i=1;i<m;i++){  //取最小时间的机器 分配工作

            if(res > a[i])

            {

                res = a[i];

                ii=i;

            }

        }

 

            a[ii]+=t[j];

        }

    }

    int res=a[0];

        for(int i=1;i<m;i++)  // 取最小时间作为 工作时间

            if(res < a[i])

            res = a[i];

        return res;

    }

}

 

void dfs(int deep){

    if(deep > n-1){ //不能用sort啊，数组脚标会对不上

          int sum=aa[0];

        for(int i=1;i<m;i++) //取最大值 作为工作时间

            if(sum < aa[i])

            sum = aa[i];

          if(res>sum)  //更新最短时间

            res = sum;

    }else{

        for(int i=0;i<m;i++){

            aa[i]+=t[deep];

            if(aa[i]<res) //剪枝 哈哈人生第一次

            dfs(deep+1);

            aa[i]-=t[deep];

        }

    }

}

 

 

int main()

{

    freopen("in.txt","r",stdin);

    cin >> n >> m;

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

        cin >> t[i];

    cout << greedy() << endl;

    dfs(0);

    cout << res;

    return 0;

}