最佳调度问题（c/c++）

Question

问题描述：假设有n个任务由k个并行工作的机器来完成。完成任务i需要的时间为Ti。试设计一个算法找出完成这n个任务的最佳调度，使得完成全部任务的时间最早。
算法设计：对任意给定的整数n和k，以及完成任务i需要的时间为Ti，i=1，2，3……n。计算完成这n个任务的最佳调度。
数据输入：由文件input.txt给出输入数据。第一行有2个正整数n和k。第2行的n个正整数是完成n个任务需要的时间。
结果输出：将计算的完成全部任务的最早时间输出到文件output.txt中。
最好能附上算法分析和复杂度分析，谢谢啊！

Answer 1

如果各机器运行速度相等，换句话就是任务无论在哪台机器上运行完成时间都相等，则问题较简单
1 . 先将任务由大到小排序
2 . 计算n个任务需要的总时间和平均到k个机器上的时间
3 . 将大于平均时间的任务各分配一个机器，找到最大完成时间
4 . 将其他任务顺序安排在一台机器上，如果时间超出最大时间，则把该任务交给下一个机器，下一个任务继续在这台机器上试安排，直到所有任务都不能在小于最大完成时间的情况下安排
5 . 安排下一台机器直道所有任务安排完，
6 . 或有可能安排某(些)任务找不到小于最大完成时间 那么重新扫描各台机器使再加上该任务后时间最小，按此方法安排万所有任物

数据结构采用链表比较合适，
K个机器k个链，n个任务按大小顺序插入一个链表，安排后从任务链表中移动到机器链表中。知道链表为空

Answer 2

这个问题的算法是贪心算法，具体证明我就没写出来了。。
我写的代码复杂度是n^2,有一个排序是nlogn,喝一个2重for循环.
但是2重for循环可以简化为for+最小堆的维护，所以最好的复杂度是NlogN,
但是懒得写最小堆了...
就这样
#include <iostream>
#include <algorithm>
using namespace std;
int a[10001];
int k_hold[10001]={};
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>a[i-1];
sort(a,a+n);
for(int i=0;i<k;i++) k_hold[i]=a[n-i-1];
for(int i=n-k-1;i>=0;i--)
{
int min=k_hold[0];
int minj=0;
for(int j=1;j<k;j++)
{
if(k_hold[j]<min)
{
min=k_hold[j];
minj=j;
}

}
k_hold[minj]+=a[i];

}
int max=k_hold[0];
for(int j=1;j<k;j++)
{
if(k_hold[j]>max)
max=k_hold[j];
}
cout<<max<<endl;
system("pause");
}

Answer 3

#include <iostream.h>
#include <iomanip.h>
#include <fstream.h>

ifstream input("input.txt");
ofstream output("output.txt");

int *t; //每个任务所需的时间序列
int best = 1000; //最优值

class Flowshop
{
public:
int N; //任务数
int M; //机器数
int *len; //每台机器所需时间序列
int* x; //当前路径
int* bestx; //最优调度：其中bestx[i]=m表示把第i项任务分配给第m台机器

void showTest()
{
input>>N; // 任务数
input>>M; //机器数目

t = new int[N];

for(int m = 0; m < N; m++)
{
input>>t[m];
}

len =new int [M]; //记录每台机器已经安排的时间
for(int j = 0; j < M; j ++)
{
len[j] = 0;
}
bestx=new int [N];
x =new int[N];

backtrack(0);

output<<best;

/* cout<<"best time:";
cout<<best<<endl;
cout<<"each job costs:";
int i;
for ( i=0;i<N;i++)
cout<<t[i]<<" ";
cout<<endl;
cout<<"best schedule:";
for ( i=0;i<N;i++)
cout<<bestx[i]<<" ";
cout<<endl;
*/

}
//回溯搜索
void backtrack (int dep)
{

if (dep==N)
{

int tmp = comp();
if(tmp<best)
{
best=tmp;
for(int i=0;i<N;i++)
{
bestx[i]=x[i];
}
}
return;
}

for(int i=0;i<M;i++)
{
len[i]+=t[dep];
x[dep]=i+1;
if(len[i]<best)
{
backtrack(dep+1);
}

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

}

//计算完成任务的时间
int comp()
{
int tmp =0;
for (int i=0;i<M;i++)
{
if(len[i]>tmp)
{
tmp=len[i];
}
}
return tmp;

}
};

void main()
{
Flowshop f;
f.showTest();
}

####################
e.g. input.txt：
7 3
2 14 4 16 6 5 3