daily pastebin goal
3%
SHARE
TWEET

SratNaToKopirovaniKusuKodu

a guest May 16th, 2018 107 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package combopt;
  2.  
  3. import java.io.*;
  4. import java.util.ArrayList;
  5. import java.util.Stack;
  6. import java.util.StringTokenizer;
  7.  
  8. public class Main {
  9.  
  10.     private BufferedReader reader;
  11.     private int n;
  12.     private int[][] input;
  13.  
  14.     ArrayList<Task> tasks;
  15.     PartialSolution currentBest;
  16.  
  17.     private final int PROCESSING_TIME = 0;
  18.     private final int RELEASE_TIME = 1;
  19.     private final int DEADLINE = 2;
  20.  
  21.     public static void main(String[] args) throws IOException {
  22.         Main main = new Main();
  23.         main.loadData(args[0]);
  24.         main.doTheBratley();
  25.         if (main.currentBest == null) {
  26.             System.out.println("-1");
  27.             main.solutionToFile(new int[]{-1}, args[1]);
  28.             return;
  29.         }
  30. //        main.currentBest.print();
  31.         int[] solution = main.constructDifferently(main.currentBest);
  32.         for (int i = 0; i < solution.length; i++) {
  33.             System.out.print(solution[i] + " ");
  34.         }
  35.         System.out.println();
  36.         main.solutionToFile(solution, args[1]);
  37.     }
  38.  
  39.     private void doTheBratley() {
  40.         // Use dfs to search the state space
  41.         Stack<PartialSolution> stack = new Stack<>();
  42.  
  43.         PartialSolution root = new PartialSolution(null, n);
  44.  
  45.         for (Task t : tasks) {
  46.             // Make first partial assignments
  47.             PartialSolution p = new PartialSolution(root, n);
  48.             p.assignTask(t);
  49.             stack.push(p);
  50.         }
  51.  
  52.         PartialSolution ps;
  53.         while (!stack.empty()) {
  54.             ps = stack.pop();
  55.  
  56.             if (ps.unusedTasks.size() == 0) {
  57.                 if (currentBest == null) {
  58.                     currentBest = ps;
  59.                 } else if (currentBest.finishTime > ps.finishTime) {
  60.                     currentBest = ps;
  61.                 }
  62.             } else {
  63.                 boolean cond1 = true;
  64.                 for (Integer i : ps.unusedTasks) {
  65.                     if (!canBeAdded(ps, tasks.get(i))) {
  66.                         cond1 = false;
  67.                         break;
  68.                     }
  69.                 }
  70.  
  71.                 if (!cond1) {
  72.                     // Didn't go through condition -> all tasks can be added to the schedule
  73.                     continue;
  74.                 } else {
  75.                     for (Integer i : ps.unusedTasks) {
  76.                         PartialSolution newPs = new PartialSolution(ps, this.n);
  77.                         newPs.assignTask(tasks.get(i));
  78.  
  79.                         if (possibleBetterSolution(newPs)) {
  80.                             if (optimalSolution(newPs)) {
  81.                                 stack = new Stack<>();
  82.                                 stack.push(newPs);
  83.                             } else {
  84.                                 stack.push(newPs);
  85.                             }
  86.                         }
  87.                     }
  88.                 }
  89.             }
  90.         }
  91.     }
  92.  
  93.     private boolean canBeAdded(PartialSolution p, Task t) {
  94.         if (p.finishTime >= t.deadline) {
  95.             return false;
  96.         } else {
  97.             if (p.finishTime < t.release) {
  98.                 return true;
  99.             } else {
  100.                 return p.finishTime + t.processTime <= t.deadline;
  101.             }
  102.         }
  103.     }
  104.  
  105.     private boolean possibleBetterSolution(PartialSolution ps) {
  106.         if (currentBest == null) {
  107.             return true;
  108.         } else {
  109.             int lb = computeLowerBound(ps);
  110.             if (lb >= currentBest.finishTime) {
  111.                 // Eliminate
  112.                 return false;
  113.             } else {
  114.                 return true;
  115.             }
  116.         }
  117.     }
  118.  
  119.     private int computeLowerBound(PartialSolution ps) {
  120.         int minR = Integer.MIN_VALUE;
  121.         int pSum = 0;
  122.         for (Integer i : ps.unusedTasks) {
  123.             pSum += tasks.get(i).processTime;
  124.             if (tasks.get(i).release < minR) {
  125.                 minR = tasks.get(i).release;
  126.             }
  127.         }
  128.         return Integer.max(minR, ps.finishTime) + pSum;
  129.     }
  130.  
  131.     private boolean optimalSolution(PartialSolution ps) {
  132.         int minReleaseOfUnused = Integer.MAX_VALUE;
  133.         for (Integer t : ps.unusedTasks) {
  134.             if (tasks.get(t).release < minReleaseOfUnused) {
  135.                 minReleaseOfUnused = tasks.get(t).release;
  136.             }
  137.         }
  138.  
  139.         if (minReleaseOfUnused == Integer.MAX_VALUE) {
  140.             // No min release found
  141.             return false;
  142.         }
  143.         if (ps.finishTime <= minReleaseOfUnused) {
  144.             return true;
  145.         } else {
  146.             return false;
  147.         }
  148.     }
  149.  
  150.     private int[] constructDifferently(PartialSolution ps) {
  151.         int[] opt = new int[ps.taskOrder.size()];
  152.         int taskID;
  153.  
  154.         for (int i = 0; i < ps.taskOrder.size(); i++) {
  155.             taskID = ps.taskOrder.get(i).id;
  156.  
  157.             if (i > 0) {
  158.                 opt[taskID] = Integer.max(tasks.get(taskID).release,
  159.                         opt[ps.taskOrder.get(i-1).id] + ps.taskOrder.get(i-1).processTime);
  160.             } else {
  161.                 opt[taskID] = Integer.max(tasks.get(taskID).release, 0);
  162.             }
  163.         }
  164.  
  165.         return opt;
  166.     }
  167.  
  168.     private int[] constructSolution(PartialSolution ps) {
  169.         int[] starts = new int[ps.taskOrder.size()];
  170.         int lastEnd = 0;
  171.         int task_id;
  172.         for (int i = 0; i < ps.taskOrder.size(); i++) {
  173.             task_id = ps.taskOrder.get(i).id;
  174.             if (i == 0) {
  175.                 starts[task_id] = tasks.get(task_id).release;
  176.                 lastEnd = starts[task_id] + tasks.get(task_id).processTime;
  177.             } else {
  178.                 if (lastEnd >= tasks.get(task_id).release) {
  179.                     starts[task_id] = lastEnd;
  180.                     lastEnd +=  tasks.get(task_id).processTime;
  181.                 } else {
  182.                     starts[task_id] = ps.taskOrder.get(i).release;
  183.                     lastEnd = ps.taskOrder.get(i).release + ps.taskOrder.get(i).processTime;
  184.                 }
  185.             }
  186.         }
  187.         return starts;
  188.     }
  189.  
  190.     private void solutionToFile(int[] res, String filePath) throws IOException {
  191.         BufferedWriter writer = new BufferedWriter(new FileWriter(filePath));
  192.         for (int i = 0; i < res.length; i++) {
  193.             writer.write(res[i] + "");
  194.             if (i < res.length - 1) {
  195.                 writer.newLine();
  196.             }
  197.         }
  198.         writer.flush();
  199.         writer.close();
  200.     }
  201.  
  202.     private void loadData(String inputPath) throws IOException {
  203.         reader = new BufferedReader(new FileReader(inputPath));
  204.  
  205.         StringTokenizer st = new StringTokenizer(reader.readLine());
  206.         n = Integer.parseInt(st.nextToken());
  207.         input = new int[n][3];
  208.         tasks = new ArrayList<>();
  209.  
  210.         for (int i = 0; i < n; i++) {
  211.             st = new StringTokenizer(reader.readLine());
  212.  
  213.             input[i][PROCESSING_TIME] = Integer.parseInt(st.nextToken());
  214.             input[i][RELEASE_TIME] = Integer.parseInt(st.nextToken());
  215.             input[i][DEADLINE] = Integer.parseInt(st.nextToken());
  216.  
  217.             Task t = new Task(i, input[i][PROCESSING_TIME], input[i][DEADLINE], input[i][RELEASE_TIME]);
  218.             tasks.add(t);
  219.         }
  220.  
  221.         currentBest = null;
  222.     }
  223. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top