[text] solution

Viewer

copydownloadembedprintName: solution
  1. package com.company;
  2.  
  3. public class Main {
  4.  
  5.     public static void main(String[] args) {
  6.         int[] tasks = new int[]{4, 4, 1, 3};
  7.         int slotTime = 4;
  8.         int result = minSlots(tasks, slotTime);
  9.         System.out.println(result);
  10.     }
  11.  
  12.     public static int minSlots(int[] tasks, int slotTime){
  13.             return minSlotsRecursion(tasks, slotTime, 0, 0, 0, new boolean[tasks.length]);
  14.     }
  15.  
  16.     public static int minSlotsRecursion(int[] tasks, int slotTime, int index, int currentSubsetSum, int totalSlots, boolean[] seen){
  17.             if(index == tasks.length){
  18.                 if(allSeen(seen))
  19.                     return totalSlots + 1;
  20.                 else if(currentSubsetSum == 0)
  21.                     return Integer.MAX_VALUE;
  22.                 else {
  23.                     //System.out.println(currentSubsetSum);
  24.                     return minSlotsRecursion(tasks, slotTime, 0, 0, totalSlots + 1, seen);
  25.                 }
  26.             }
  27.             //include
  28.             int include = Integer.MAX_VALUE;
  29.             if(!seen[index] && currentSubsetSum + tasks[index] <= slotTime){
  30.                 seen[index] = true;
  31.                 include = minSlotsRecursion(tasks, slotTime, index + 1, currentSubsetSum + tasks[index], totalSlots, seen);
  32.                 seen[index] = false;
  33.             }
  34.            //exclude
  35.            int exclude = minSlotsRecursion(tasks, slotTime, index + 1, currentSubsetSum, totalSlots, seen);
  36.            return Math.min(include, exclude);
  37.     }
  38.  
  39.     public static boolean allSeen(boolean[] seen){
  40.         for (int i = 0; i < seen.length; i++){
  41.             if(!seen[i])
  42.                 return false;
  43.         }
  44.         return true;
  45.     }
  46. }
  47.  

Editor

You can edit this paste and save as new:


File Description
  • solution
  • Paste Code
  • 10 Aug-2022
  • 1.69 Kb
You can Share it: