您好我是编程方面的新手,需要指导 .
我们在种植园 . 我有许多字段包含不同数量的树 . 在每个字段上都必须完成一组任务 . 任务相同但时间不同,因为字段大小不同 . 我想生成一个与最佳工作时间匹配的任务列表 .
我相信这是一个Job Shop调度问题(NP-hard),但据我所知,它可以用蛮力搜索解决,因为数据集很小 . 如何在指定时间内生成所有组合并返回最佳拟合?我试着看一些伪代码,但坦率地说我很丢失,我的尝试相当差:
//暴力搜索
// 1. first(P): generate a first candidate solution for P.
// 2. next(P,c): generate the next candidate for P after the current one c.
// 3. valid(P,c): check whether candidate c is a solution for P-
// 4. output(P,c): use the solution c of P as appropriate to the application.
public static ArrayList<Task> generatedList2(int totalTime) {
ArrayList<Task> bestFit = new ArrayList<>();
ArrayList<Task> tmpFit = new ArrayList<>();
int tmpTime = 0;
int bestFitTime = -1;
Task testTask = new Task("TestTask", 0);
bestFit.add(testTask); //1
for(Field f : fields) { //2
for(Task t : f.getUndoneTasks()) {
if(f.getTaskTime(t) < totalTime) {
tmpFit.add(t);
tmpTime += f.getTaskTime(t);
totalTime -= f.getTaskTime(t);
}
}
if(tmpTime < bestFitTime) { //3
bestFit = new ArrayList<Task>(tmpFit);
bestFitTime = tmpTime;
tmpFit.clear();
}
else {
tmpFit.clear();
}
}
return bestFit; //4
}
更新方案:
public static ArrayList<Task> RecursivelyGetAnswer(ArrayList<Task> listSoFar,
ArrayList<Task> masterList, ArrayList<Task> bestList, int limit, int index) {
for (int i = index; i < masterList.size(); i++) {
Task task = masterList.get(i);
double listSoFarTotal = getTotal(listSoFar) + task.getTaskLength();
if (listSoFarTotal <= limit) {
int bestListTotal = getTotal(bestList);
listSoFar.add(task);
if (listSoFarTotal > bestListTotal) {
bestList = new ArrayList<Task>(listSoFar);
}
else if(100 - ((float) (limit - bestListTotal)/bestListTotal * 100) > 95) {
break;
}
bestList = RecursivelyGetAnswer(listSoFar, masterList, bestList, limit, i+1);
listSoFar.remove(task);
}
}
return bestList;
}
1 回答
我想出了一个递归解决方案 . 出于我的解决方案的目的,我假设您只有一个任务列表,而不是字段内的任务 .