11

For an application I'm working on I need something like a packing algorithm implemented in Python see here for more details. The basic idea is that I have n objects of varying sizes that I need to fit into n bins, where the number of bins is limited and the size of both objects and bins is fixed. The objects / bins can be either 1d or 2d, interested in seeing both. (I think 3d objects is probably more than I need.)

I know there are a variety of algorithms out there that address this problem, such asBest Fit Decreasing and First Fit Decreasing, but I was hoping there might be an implementation in Python (or PHP/C++/Java, really I'm not that picky). Any ideas?

tchaymore
  • 3,728
  • 13
  • 55
  • 86
  • Is this in 2d? what kind of shapes? limited to rectangles? – jterrace Sep 12 '11 at 18:35
  • It would help if you could answer these questions - 1. What is the maximum number of objects? 2. What is the maximum number of bins? 3. What is the maximum width/height of an object? – Prav Sep 12 '11 at 18:40
  • I can't give you an exact number for the maximum number of objects or bins, but I'm thinking that the max would be around 20-30 (for each). As far as width/height goes, can't give you max right now. – tchaymore Sep 12 '11 at 18:45

1 Answers1

13

https://bitbucket.org/kent37/python-tutor-samples/src/f657aeba5328/BinPacking.py

""" Partition a list into sublists whose sums don't exceed a maximum 
    using a First Fit Decreasing algorithm. See
    http://www.ams.org/new-in-math/cover/bins1.html
    for a simple description of the method.
"""


class Bin(object):
    """ Container for items that keeps a running sum """
    def __init__(self):
        self.items = []
        self.sum = 0

    def append(self, item):
        self.items.append(item)
        self.sum += item

    def __str__(self):
        """ Printable representation """
        return 'Bin(sum=%d, items=%s)' % (self.sum, str(self.items))


def pack(values, maxValue):
    values = sorted(values, reverse=True)
    bins = []

    for item in values:
        # Try to fit item into a bin
        for bin in bins:
            if bin.sum + item <= maxValue:
                #print 'Adding', item, 'to', bin
                bin.append(item)
                break
        else:
            # item didn't fit into any bin, start a new bin
            #print 'Making new bin for', item
            bin = Bin()
            bin.append(item)
            bins.append(bin)

    return bins


if __name__ == '__main__':
    import random

    def packAndShow(aList, maxValue):
        """ Pack a list into bins and show the result """
        print 'List with sum', sum(aList), 'requires at least', (sum(aList)+maxValue-1)/maxValue, 'bins'

        bins = pack(aList, maxValue)

        print 'Solution using', len(bins), 'bins:'
        for bin in bins:
            print bin

        print


    aList = [10,9,8,7,6,5,4,3,2,1]
    packAndShow(aList, 11)

    aList = [ random.randint(1, 11) for i in range(100) ]
    packAndShow(aList, 11)
Alex L
  • 8,748
  • 5
  • 49
  • 75
rocksportrocker
  • 7,251
  • 2
  • 31
  • 48
  • 3
    Well, this is false with `aList = [5, 4, 4, 3, 2, 2]` and `maxValue = 10`. It gives result with 3 boxes, but the true answer should be 2 ([4, 4, 2], [5, 3, 2]). – aemdy Feb 24 '13 at 20:38
  • 3
    @aemdy Says who? The FFD algorithm would give [5 4], [4 3 2], [2 2]. Optimal bin packing is NP-hard and exact algorithms to do that are more complicated. – krapht Nov 14 '14 at 17:49
  • 1
    This works well; I modified this to simplify my lineal materials purchasing: https://github.com/ninowalker/linear-pack – Nino Walker Jul 26 '15 at 07:58
  • `http://www.ams.org/new-in-math/cover/bins1.html` This link is broken. Also, just a suggestion: While assigning bins to items, you can pick the bin which has enough capacity to contain the item, but at the same time has the least remaining capacity among all the bins. It will give a more optimal answer. – Anmol Singh Jaggi Aug 16 '20 at 06:54