回溯法--最佳调度问题
#include<fstream>
#include<iostream>
#include <string>
using namespace std;
ifstream fin("input.txt");
ofstream fout("output.txt");
int n,k,best;
int len[99];
int t[99];
int comp()
{
int tmp=0;
for(int i=0;i<k;i++)if(len[i]>tmp)tmp=len[i];
return tmp;
}
void search(int dep,int *len,int *t)
{
if(dep==n){
int tmp=comp();
if(tmp<best)best=tmp;
return;
}
for(int i=0;i<k;i++){
len[i]+=t[dep];
if(len[i]<best) search(dep+1,len,t);
len[i]-=t[dep];
}
}
int main()
{
int i;
fin>>n;
fin>>k;
for (int i=0;i<n;i++)
fin>>t[i];
for (i=0;i<k;i++)
len[i]=0;
search(0,len,t);
fout<<best<<endl;
return 0;
}
