Grouping of items based on criteria
<p>I have a list of items:</p>

<pre><code>ShelvesToPack = [{'ShelfLength': 2278.0, 'ShelfWidth': 356.0, 'ShelfArea': 759152.0, 'ItemNames': 1},
{'ShelfLength': 1220.0, 'ShelfWidth': 610.0, 'ShelfArea': 372100.0, 'ItemNames': 2},
{'ShelfLength': 2310.0, 'ShelfWidth': 762.0, 'ShelfArea': 1760220.0, 'ItemNames': 3},
{'ShelfLength': 610.0, 'ShelfWidth': 610.0, 'ShelfArea': 1450435.0, 'ItemNames': 4}]
</code></pre>

<p>I need the program that tells how many minimum number of groups one can have and how the items are grouped.</p>

<p>I would like to form groups of these items such that sum of shelflength of items &lt;= max length or sum of shelfwidth of items  &lt;= max width and sum of ShelfArea of items &lt;= Max Area. In this case, if we look at the logic we can have all the items packed in minimum 2 groups - item 1 and 3 will form one group and item 2 &amp; 4 will form other group. I would like to have the answer in the format:</p>

<pre><code>[[{'ShelfLength': 2278.0, 'ShelfWidth': 356.0, 'ShelfArea': 759152.0, 'ItemNames': 1} ,
 {'ShelfLength': 2310.0, 'ShelfWidth': 762.0, 'ShelfArea': 1760220.0, 'ItemNames': 3}],
[{'ShelfLength': 1220.0, 'ShelfWidth': 610.0, 'ShelfArea': 372100.0, 'ItemNames': 2},
 , {'ShelfLength': 610.0, 'ShelfWidth': 610.0, 'ShelfArea': 1450435.0, 'ItemNames': 4}]]
</code></pre>

<p>I have written a code but it does not give the result I wanted.</p>

<pre><code>ShelvesToPack_sorted = sorted(ShelvesToPack, key = itemgetter('ShelfWidth'), reverse = True)
AreaOfObject = 2972897.28
current_width = 0
current_length = 0
current_area = 0
ply =[]
plywoods=[]
for item in ShelvesToPack_sorted:
    if (current_width + item['ShelfWidth'] &lt;= 1219.2  or  current_length + item['ShelfLength'] &lt;= 2438.5) and  current_area + item['ShelfArea'] &lt;= AreaOfObject:
        ply.append(item)
        current_width += item['ShelfWidth']
        current_length += item['ShelfLength']
        current_area += item['ShelfArea']
    else:
       plywoods.append(ply)
       if (item['ShelfWidth'] &lt;= 1219.2  or item['ShelfLength'] &lt;= 2438.5) and item['ShelfArea'] &lt;= AreaOfObject:
           ply = [item]
           current_width = item['ShelfWidth']
           current_length = item['ShelfLength']
           current_area = item['ShelfArea']
       else:
           ply = []
           current_width = 0
           current_length = 0
           current_area = 0

if ply:
    plywoods.append(ply)

print(plywoods)
</code></pre>

<p>I have got the following output which is not quite right and I am unable to do the correct grouping.</p>

<pre><code>[[{'ItemNames': 3, 'ShelfWidth': 762.0, 'ShelfLength': 310.0, 'ShelfArea': 1760220.0}],
 [{'ItemNames': 2, 'ShelfWidth': 610.0, 'ShelfLength': 1220.0, 'ShelfArea': 372100.0},
  {'ItemNames': 4, 'ShelfWidth': 610.0, 'ShelfLength': 610.0, 'ShelfArea': 1450435.0}],
 [{'ItemNames': 1, 'ShelfWidth': 356.0, 'ShelfLength': 2278.0, 'ShelfArea': 759152.0}]]
</code></pre>

<p>Can anyone please suggest?</p>

<p>Here's something that appears to work correctly. Since the order of shelves in a combination doesn't matter, it simply does things using a brute-force approach that checks every possible combination of the shelves. Because there may be a very large number of them to process, it's important to write code which is fairly efficient. There are probably more optimal algorithms that would accomplishing this fasterâin what is essentially a searching or path-finding problem. </p>

<p>With that in mind and to make accessing the fields in each shelf dictionary easier, it first converts them all into an equivalent list of <code>namedtuple</code> instances which are used by the code from that point on. (If you really need them in dictionary form, it would be simple to keep a copy of it around or recreate it when necessary.)</p>

<p>Once the conversion is done, it then checks all combinations of shelf items in the range from 1 to all of them. It stores these it finds in a list named <code>groups</code>. <code>group[N]</code> will contain a sublist of the combinations of <code>N</code> items that met the criteria. (And the length of that sublist is the number of combinations of that number of shelves found, of course).</p>

<p>So, for example, in the output far below, it shows that there were 4 groups of 2 items that meet the criteria. (It doesn't print each combination of them, however.)</p>

<pre><code>from collections import namedtuple
from itertools import combinations
from operator import itemgetter

shelves_to_pack = [
    {'ShelfLength': 2278.0, 'ShelfWidth': 356.0, 'ShelfArea': 759152.0, 'ItemNames': 1},
    {'ShelfLength': 1220.0, 'ShelfWidth': 610.0, 'ShelfArea': 372100.0, 'ItemNames': 2},
    {'ShelfLength': 2310.0, 'ShelfWidth': 762.0, 'ShelfArea': 1760220.0, 'ItemNames': 3},
    {'ShelfLength': 610.0, 'ShelfWidth': 610.0, 'ShelfArea': 1450435.0, 'ItemNames': 4}]

# convert dict list into a namedtuple list to simplify field access
Shelf = namedtuple('Shelf',
                   'length width area item_names')
shelves = [Shelf(length=shelf['ShelfLength'], width=shelf['ShelfWidth'],
                 area=shelf['ShelfArea'], item_names=shelf['ItemNames'])
            for shelf in shelves_to_pack]

MAX_WIDTH, MAX_LENGTH = 1219.2, 2438.5
MAX_AREA = 2972897.28

def meets_criteria(shelf_combo):
    """ Determine if shelf combination meets criteria. """
    return (sum(shelf.area for shelf in shelf_combo) &lt;= MAX_AREA
            and (sum(shelf.length for shelf in shelf_combo) &lt;= MAX_LENGTH
                 or sum(shelf.width for shelf in shelf_combo) &lt;= MAX_WIDTH))

groups = [[]]  # first group representing zero shelf items is always empty
for num_shelves in range(1, len(shelves)+1):
    groups.append([combo for combo in combinations(shelves, num_shelves)
                      if meets_criteria(combo)])
for i, group in enumerate(groups):
    print('groups of {} items: size {}'.format(i, len(group)))
</code></pre>

<p>This is the output generated from the code and input data above:</p>

<pre class="lang-none prettyprint-override"><code>groups of 0 items: size 0
groups of 1 items: size 4
groups of 2 items: size 4
groups of 3 items: size 0
groups of 4 items: size 0
</code></pre>

python python-3.x