title: Group list of objects into smallest possible number of sublists without exceeding maximum sum
body: <p>I'm trying to write a method that groups objects into the minimum amount of sublists without mixing types (int field on object) or the sum of their values exceeding a defined maximum value. It should look something like this:</p>
  <pre><code>List&lt;List&lt;Foo&gt;&gt; group(List&lt;Foo&gt; values, int maximumValue);
  </code></pre>
  <p>This is my pojo class (actual sample code at the bottom includes constructor and accessors):</p>
  <pre><code>public class Foo {
      int type;
      int value;
  }
  </code></pre>
  <p>Here is a sample input and the expected output:</p>
  <p>Input:</p>
  <pre><code>maximumValue=50
  Foo [type=1, value=27]
  Foo [type=1, value=24]
  Foo [type=1, value=18]
  Foo [type=1, value=13]
  Foo [type=1, value=10]
  Foo [type=1, value=7]
  Foo [type=2, value=39]
  Foo [type=2, value=34]
  Foo [type=2, value=15]
  Foo [type=2, value=5]
  </code></pre>
  <p>Expected output:</p>
  <pre><code>Foo [type=1, value=27]
  Foo [type=1, value=13]
  Foo [type=1, value=10]
  sum=50
  Foo [type=1, value=24]
  Foo [type=1, value=18]
  Foo [type=1, value=7]
  sum=49
  Foo [type=2, value=39]
  Foo [type=2, value=5]
  sum=44
  Foo [type=2, value=34]
  Foo [type=2, value=15]
  sum=49
  </code></pre>
  <p>When trying to implement my grouping method I found this answer which already seemed very close to what I need: <a href="https://stackoverflow.com/questions/13662829/rearrange-int-array-sort-into-groups-with-a-sum-maximum-in-java/13664211#13664211">Rearrange int array, sort into groups with a sum maximum in Java</a></p>
  <p>My current implementation is essentially the same, just adjusted for using an object instead of directly grouping integers plus separation by type:</p>
  <pre><code>public List&lt;List&lt;Foo&gt;&gt; group(List&lt;Foo&gt; values, int maximumValue) {                     
    List&lt;List&lt;Foo&gt;&gt; sublists = new ArrayList&lt;&gt;();                                               
    // at first group by type                                                                   
    Map&lt;?, List&lt;Foo&gt;&gt; typeGroups = values.stream().collect(Collectors.groupingBy(Foo::getType));
    for (List&lt;Foo&gt; input : typeGroups.values()) {                                               
      input.sort(Comparator.comparingInt(Foo::getValue));                                       
      List&lt;List&lt;Foo&gt;&gt; result = new ArrayList&lt;&gt;();                                               
      result.add(new ArrayList&lt;Foo&gt;());                                                         
      // Initialize the sums of the groups, to increase performance (I guess).                  
      ArrayList&lt;Integer&gt; sums = new ArrayList&lt;&gt;();                                              
      sums.add(0);                                                                              
      while (!input.isEmpty()) {                                                                
        Foo foo = input.get(0);                                                                 
        int value = foo.getValue();                                                             
        boolean match = false;                                                                  
        // Search the next groups and check if our current                                      
        // number ('n') fits.                                                                   
        for (int i = 0; i &lt; sums.size(); i++) {                                                 
          if (sums.get(i) + value &lt;= maximumValue) {                                            
            // If it fits, then add the number to the group.                                    
            sums.set(i, sums.get(i) + value);                                                   
            result.get(i).add(foo);                                                             
            match = true;                                                                       
            break;                                                                              
          }                                                                                     
        }                                                                                       
        // If 'n' doesn't fit in any group, create a new one.                                   
        if (!match) {                                                                           
          List&lt;Foo&gt; newGroup = new ArrayList&lt;&gt;();                                               
          newGroup.add(foo);                                                                    
          result.add(newGroup);                                                                 
          sums.add(value);                                                                      
        }                                                                                       
        // Remove our number.                                                                   
        input.remove(0);                                                                        
      }                                                                                         
      sublists.addAll(result);                                                                  
    }                                                                                           
    return sublists;                                                                            
  }
  </code></pre>
  <p>Calling this function with the sample input from earlier gives me the following output:</p>
  <pre><code>Foo [type=1, value=7]
  Foo [type=1, value=10]
  Foo [type=1, value=13]
  Foo [type=1, value=18]
  sum=48
  Foo [type=1, value=24]
  sum=24
  Foo [type=1, value=27]
  sum=27
  Foo [type=2, value=5]
  Foo [type=2, value=15]
  sum=20
  Foo [type=2, value=34]
  sum=34
  Foo [type=2, value=39]
  sum=39
  </code></pre>
  <p>Those are 6 groups but it is possible (as seen in the example earlier) to group the input into only 4 groups. I tried reversing the sort order from ascending to descending which improves the result to 5 groups but doesn't fix the underlying issue whatsoever and still isn't even the smallest possible number of groups.</p>
  <p>Here is small self-contained class I wrote for testing &amp; adjusting:</p>
  <pre><code>import java.util.ArrayList;
  import java.util.Comparator;
  import java.util.List;
  import java.util.Map;
  import java.util.stream.Collectors;
  
  public class ObjectGrouping {
  
    public static void main(String[] args) {
      int maximumValue = 50;
      List&lt;Foo&gt; values = new ArrayList&lt;&gt;();
      values.add(new Foo(1, 27));
      values.add(new Foo(1, 24));
      values.add(new Foo(1, 18));
      values.add(new Foo(1, 13));
      values.add(new Foo(1, 10));
      values.add(new Foo(1, 7));
      // ideal groups: [27, 13, 10], [24, 18, 7]
      values.add(new Foo(2, 39));
      values.add(new Foo(2, 34));
      values.add(new Foo(2, 15));
      values.add(new Foo(2, 5));
      // ideal groups: [39, 15], [34, 5] (which way exactly doesn't matter as long as it's 2 groups)
      System.out.println(&quot;input:&quot;);
      values.forEach(System.out::println);
      System.out.println();
      System.out.println();
      List&lt;List&lt;Foo&gt;&gt; result = group(values, maximumValue);
      System.out.println(&quot;result:&quot;);
      for (List&lt;Foo&gt; list : result) {
        list.forEach(System.out::println);
        // check if all objects are of the same group
        assert list.stream().map(Foo::getType).distinct().count() == 1;
        // check if sum of values does not exceed maximum value
        int sum = list.stream().mapToInt(Foo::getValue).sum();
        System.out.println(&quot;sum=&quot; + sum);
        assert sum &lt;= maximumValue;
      }
    }
  
    public static List&lt;List&lt;Foo&gt;&gt; group(List&lt;Foo&gt; values, int maximumValue) {
      List&lt;List&lt;Foo&gt;&gt; sublists = new ArrayList&lt;&gt;();
      // at first group by type
      Map&lt;?, List&lt;Foo&gt;&gt; typeGroups = values.stream().collect(Collectors.groupingBy(Foo::getType));
      for (List&lt;Foo&gt; input : typeGroups.values()) {
        input.sort(Comparator.comparingInt(Foo::getValue));
        List&lt;List&lt;Foo&gt;&gt; result = new ArrayList&lt;&gt;();
        result.add(new ArrayList&lt;Foo&gt;());
        // Initialize the sums of the groups, to increase performance (I guess).
        ArrayList&lt;Integer&gt; sums = new ArrayList&lt;&gt;();
        sums.add(0);
        while (!input.isEmpty()) {
          Foo foo = input.get(0);
          int value = foo.getValue();
          boolean match = false;
          // Search the next groups and check if our current
          // number ('n') fits.
          for (int i = 0; i &lt; sums.size(); i++) {
            if (sums.get(i) + value &lt;= maximumValue) {
              // If it fits, then add the number to the group.
              sums.set(i, sums.get(i) + value);
              result.get(i).add(foo);
              match = true;
              break;
            }
          }
          // If 'n' doesn't fit in any group, create a new one.
          if (!match) {
            List&lt;Foo&gt; newGroup = new ArrayList&lt;&gt;();
            newGroup.add(foo);
            result.add(newGroup);
            sums.add(value);
          }
          // Remove our number.
          input.remove(0);
        }
        sublists.addAll(result);
      }
      return sublists;
    }
  
    public static class Foo {
  
      private int type;
      private int value;
  
      public Foo(int type, int value) {
        this.type = type;
        this.value = value;
      }
  
      public int getType() {
        return type;
      }
  
      public int getValue() {
        return value;
      }
  
      public void setType(int type) {
        this.type = type;
      }
  
      public void setValue(int value) {
        this.value = value;
      }
  
      @Override
      public String toString() {
        return &quot;Foo [type=&quot; + type + &quot;, value=&quot; + value + &quot;]&quot;;
      }
    }
  }
  </code></pre>
  <p>I would be fine with either fixing the existing algorithm or using a completely new one, I was thinking that it might be possible to use the Streams API and implement a custom Collector but not sure. Any help is greatly appreciated, thanks.</p>