Bin packing problem - First Fit Decreasing Algorithm

bin_packing_first_fit_decreasing_algorithm.py

import numpy as np
from __future__ import division
from collections import namedtuple

class ObjectWrapper(object):
    def __init__(self, obj, weight_call):
        self.obj = obj
        self.weight_call = weight_call
        
    @property
    def weight(self):
        attr = getattr(self.obj, self.weight_call)
        if callable(attr):
            return attr()
        return attr
    
    def __repr__(self):
        return 'ObjectWrapper(Object: {}, weight: {})'.format(self.obj, self.weight)
    
class Bin(object):
    """ Container for items that keeps a running sum """

    def __init__(self, obj, capacity_pct=1.0):
        self.objects = [obj]
        self.weight = obj.weight
        self.capacity_pct = capacity_pct

    def append(self, obj, capacity_pct):
        self.objects.append(obj)
        self.weight += obj.weight
        self.capacity_pct += capacity_pct

    def __repr__(self):
        return 'Bin(weight: {}, objects: {})'.format(self.weight, repr(self.objects))


def bin_pack(objects, total_weight_bin, min_capacity_pct=None, max_capacity_pct=None):
    """ First Fit Decreasing algorithm. """
    objects.sort(key=lambda o: o.weight, reverse=True)

    if not max_capacity_pct:
        max_capacity_pct = np.ceil(objects[0].weight / total_weight_bin)

    if not min_capacity_pct:
        min_capacity_pct = 0
    
    bins = list()
    incomplete_bins = list()
    for i, obj in enumerate(objects):
        capacity_pct = obj.weight / total_weight_bin
        for b in incomplete_bins:            
            if b.capacity_pct > min_capacity_pct:
                if b.capacity_pct + capacity_pct > max_capacity_pct:
                    continue
            elif b.capacity_pct + capacity_pct > min_capacity_pct:
                continue
            b.append(obj, capacity_pct)

            if b.weight % total_weight_bin == 0:
                incomplete_bins.remove(b)
                bins.append(b)
            break
        else:            
            b = Bin(obj, capacity_pct)
            if b.weight % total_weight_bin == 0:
                bins.append(b)
            else:
                incomplete_bins.append(b)

    for b in incomplete_bins:
        for obj in objects:
            capacity_pct = obj.weight / total_weight_bin
            if b.capacity_pct + capacity_pct > min_capacity_pct:
                continue
            b.append(obj, capacity_pct)

            if b.weight % total_weight_bin == 0:
                bins.append(b)
    return bins

Block = namedtuple('Block', 'name value')

blocks = [Block('A', 4), Block('B', 1), Block('C', 2), Block('D', 5), Block('E', 3), Block('H', 6), Block('F', 2), Block('G', 3), Block('I', 3)]
objs = [ObjectWrapper(b, 'value') for b in blocks]
bins = bin_pack(objs, 6)

for b in bins:
    print [o.obj.name for o in b.objects], b.weight