Hello I am relative new in programming and need guidance.
We are on a plantage. I have a number of Fields that contain different amounts of trees. On each field a set of tasks have to be done. The tasks are the same but the time varies since the fields are different sizes. I want to generate a list of tasks that matches the assigned working time for the day best.
I believe this is a Job Shop scheduling problem (NP-hard) but as far as i know it can be solved with brute-force search since the data set is small. How do I generate all combinations within the assigned time and return the best fit? I tried to look at some pseudo code but frankly im quite lost and my attempt is rather poor:
//Brute-force search
// 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
}
Updated solution:
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;
}
I came up with a recursive solution. For the purposes of my solution, I assumed that you just had a list of tasks, instead of tasks inside fields.
import java.util.ArrayList;
class Task
{
public int taskLength;
public Task(int taskLength)
{
this.taskLength = taskLength;
}
@Override
public String toString()
{
return "T" + taskLength;
}
}
public class Answers
{
public static void main(String args[])
{
ArrayList masterList = new ArrayList();
//Add some sample data
masterList.add(new Task(555));
masterList.add(new Task(1054));
masterList.add(new Task(888));
masterList.add(new Task(5923));
masterList.add(new Task(2342));
masterList.add(new Task(6243));
masterList.add(new Task(9227));
masterList.add(new Task(4111));
masterList.add(new Task(4322));
masterList.add(new Task(782));
final int limit = 9999;
ArrayList<Task> bestList = RecursivelyGetAnswer(new ArrayList<>(), masterList, new ArrayList<>(), limit, 0);
System.out.println(bestList.toString());
System.out.println(getTotal(bestList));
}
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);
if (getTotal(listSoFar) + task.taskLength <= limit)
{
listSoFar.add(task);
if (getTotal(listSoFar) > getTotal(bestList))
{
bestList = new ArrayList(listSoFar);
}
bestList = RecursivelyGetAnswer(listSoFar, masterList, bestList, limit, i+1);
listSoFar.remove(task);
}
}
return bestList;
}
// Given a list of tasks, get the sum of the lengths of the tasks.
public static int getTotal(ArrayList<Task> myList)
{
int sum = 0;
for (Task t:myList)
sum += t.taskLength;
return sum;
}
}