Java: batch integers

Question

I was wondering what the best way is to execute a given set of numbers in terms of processing time. Take the items: 9, 18, 7, 8, 4, 9, 11, 15, 3, 8, (item 1 has a processing time of 9, item 2 has a processing time of 18, etc.).

If the batch processing time limit is set to 20, then a possible grouping of elements in a batch will be: {1, 3, 5} {2} {4, 6} {8, 9} {7, 10} (group 1 is 9 + 7 + 4 = 20) etc., so that 5 batches of elements were where the content is <= 20.

Ideally, I want him to sort them in as few groups as possible. The above case is a minimum of 5 groups with a content limit of 20 ...

thanks

Answer 1

If the batch processing time limit is set to 20, ...

Therefore, I assume that there is no element that exceeds the processing time limit of a batch. Here is my approach:

• Sort the elements first. Then get 2 pointers for the list, one at index 0 (left pointer), and the second at the last index (right pointer).
• Take the right pointer element and add it to the sublist. Take the left pointer element and add it to the same sublist. If the sum of the items in the sublist is less than the limit, update the left pointer (set this to the next item) and try adding it. Continue this process until the sublist is populated.
• Then start filling out the next sublist. Use all the elements to build subscriptions.

Java implementation:

 int[] input = { 9, 18, 7, 8, 4, 9, 11, 15, 3, 8 }; // Input items. Arrays.sort(input); // Sort the items. int left = 0, right = input.length - 1; // Left and right pointers. int remainder = 0, limit = 20; // list of groups. ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>(); while (right >= left) { ArrayList<Integer> subList = new ArrayList<Integer>(); list.add(subList); // Add the current maximum element. subList.add(input[right]); if (right == left) break; remainder = limit - input[right]; right--; // Add small elements until limit is reached. while (remainder > input[left]) { subList.add(input[left]); remainder = remainder - input[left]; left++; } remainder = 0; // Reset the remainder. } 

Group Printing:

 for (ArrayList<Integer> subList : list) { for (int i : subList) System.out.print(i + " "); System.out.println(); } 

Conclusion: (Each line denotes a group of numbers)

 18 15 3 11 4 9 7 9 8 8 

Answer 2

• Take the largest of the IN set and put the new set S. (item 2, value 18)
• Try to find the largest element with a value of <= (20 - 18): none, add S to the list of sets.
• if IN is not empty GOTO 1

Iterations:

  IN: 9, 18, 7, 8, 4, 9, 11, 15, 3, 8 S1 (18) : 2:18 IN: 9, _, 7, 8, 4, 9, 11, 15, 3, 8 S2 (19) : 8:15, 5:4 IN: 9, _, 7, 8, _, 9, 11, _, 3, 8 S3 (20) : 7:11, 1:9 IN: _, _, 7, 8, _, 9, _, _, 3, 8 S4 (20) : 6: 9, 4:8, 0:3 IN: _, _, 7, _, _, _, _, _, _, 8 S5 (15) : 10: 8, 3:7 IN: _, _, _, _, _, _, _, _, _, _ 

The code:

 public class Knapsack { public static void knapsack( int capacity, int[] values, List< int[] > indices ) { int[] in = Arrays.copyOf( values, values.length ); List< Integer > workspace = new LinkedList<>(); int wCapacity = capacity; boolean inProgress = true; while( inProgress ) { int greatestValue = -1; int greatestIndex = -1; for( int i = 0; i < in.length; ++i ) { int value = in[i]; if( value > Integer.MIN_VALUE && greatestValue < value && value <= wCapacity ) { greatestValue = value; greatestIndex = i; } } if( greatestIndex >= 0 ) { workspace.add( greatestIndex ); in[greatestIndex] = Integer.MIN_VALUE; wCapacity -= greatestValue; } else if( workspace.isEmpty()) { inProgress = false; } else { int[] ws = new int[workspace.size()]; for( int i = 0; i < workspace.size(); ++i ) { ws[i] = workspace.get(i).intValue(); } indices.add( ws ); workspace = new LinkedList<>(); wCapacity = capacity; } } } static void print( int[] values, List< int[] > indices ) { int r = 0; for( int[] t : indices ) { String items = ""; int sum = 0; for( int index : t ) { int value = values[index]; if( ! items.isEmpty()) { items += ", "; } items += index + ":" + value; sum += value; } System.out.println( "S" + ++r + " (" + sum + ") : " + items ); } } public static void main( String[] args ) { int[] values = { 9, 18, 7, 8, 4, 9, 11, 15, 3, 8 }; List< int[] > indices = new LinkedList<>(); knapsack( 20, values, indices ); print( values, indices ); } } 

Result:

 S1 (18) : 1:18 S2 (19) : 7:15, 4:4 S3 (20) : 6:11, 0:9 S4 (20) : 5:9, 3:8, 8:3 S5 (15) : 9:8, 2:7