Hola, soy relativamente nuevo en programación y necesito orientación.

Estamos en una plantación. Tengo varios campos que contienen diferentes cantidades de árboles. En cada campo se debe realizar un conjunto de tareas. Las tareas son las mismas pero el tiempo varía ya que los campos son de diferentes tamaños. Quiero generar una lista de tareas que coincida mejor con el tiempo de trabajo asignado para el día.

Creo que este es un problema de programación de Job Shop (NP-difícil) pero, que yo sepa, se puede resolver con una búsqueda de fuerza bruta ya que el conjunto de datos es pequeño. ¿Cómo genero todas las combinaciones dentro del tiempo asignado y devuelvo la que mejor se ajusta? Traté de mirar un pseudocódigo pero, francamente, estoy bastante perdido y mi intento es bastante pobre:

//Búsqueda de fuerza bruta

 // 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 }

Solución actualizada:

 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; }