Java: batching integers

Question

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

Trusting

Sounds like a variant of Knapsack: en.wikipedia.org/wiki/Knapsack_problem – Conglomeration

This is a variant of the Knapsack problem -- its called the Bin Packing Problem. It's NP-hard, but there are greedy approximation schemes, one outlined on the linked wiki article. – Shayneshays

Given that the problem is NP-hard, how large is the largest problem you need to solve, and are you expecting to get the optimal solution? – Metcalf

Answer 1

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

So I assume that there is no element greater than batch processing time limit. Here is my approach:

• Firstly sort the items. Then get 2 pointers for the list, one is at index 0 (left-pointer) and the other one at the last index (right-pointer).
• Take the element of right-pointer and add it to a sublist. Take the element of left-pointer and add it to the same sublist. If the sum of the elements in sublist is less than limit, update left-pointer (set it to next element) and try adding it. Continue this process until a sublist is filled.
• Then start filling the next sublist. Consume all elements to construct sublists.

Implementation in Java:

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.
}

Printing the groups:

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

Output: (Each line denotes a group of numbers)

18 
15 3 
11 4 
9 7 
9 8
8

Tellurite

This sounds an interesting approach. How would this be coded in java? – Trusting

@qwertyRocker I was just trying to code it in Java, I'll update my answer when finished =) – Tellurite

Nice code :) works great. You've implemented it better than i could have expected. Thanks again for your help. – Trusting

Just one more thing, i have just noticed it misses out one of the items in the array? only prints 9 out of the 10 items? – Trusting

This implementation take the greatest and then the smallest, it's not optimal – Diaper

@qwertyRocker ahh sorry, updated my code. by the way, my solution is not the best, it might not find optimal ones. – Tellurite

@Diaper you are right, I just wanted to take a different approach to solve it. – Tellurite

Yes, i know its not optimal, but a great solution none the less :D Thanks again guys. – Trusting

Answer 2

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 = 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 );
   }
}

The 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

Diaper

This is also very nice code. Both these answers have taught me a lot. I wish i could accept two answers. Thanks for your time and help :D – Trusting