Alex Rivera | Logout

Java: batching integers

Asked 2012-11-28T19:57:32.430
8

I was wondering what the best way is to batch a given set of numbers in terms of a processing time. Take 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 say 20, then a possible grouping of the items into batches would be:{1, 3, 5} {2} {4, 6} {8, 9} {7, 10} (group 1 is 9+7+4=20) etc so 5 batches of items have been made where the contents are <= 20.

Ideally i want it to sort them into as fewer groups as possible. Above's case is a minimum of 5 groups with a content limit of 20...

Thanks

java integer batching
Edit
Report

1 Answer

3
  1. Take the biggest from the IN set and put in a new set S. (item 2, value 18)
  2. Try to find the biggest item with value <= (20 - 18): none, add S to a list of set.
  3. 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
answered 2012-11-28T20:14:47.070

Your Answer