binpackage.py

#!/usr/bin/env python

"""
http://en.wikipedia.org/wiki/Bin_packing_problem
"""

import os, sys, random

def empaquetar_ordenado(E, L, Ordenar=True):
    if Ordenar:
        ordenados = sorted(E)
    else:
        ordenados = list(E)

    resul = []
    while len(ordenados) > 0:
        i = 0
        actual = []
        actual_suma = 0
        while i < len(ordenados) and actual_suma < L:
            if ordenados[i] <= (L - actual_suma):
                actual.append(ordenados[i])
                actual_suma += ordenados[i]
                del ordenados[i]
            else:
                i = i + 1
        resul.append(actual)

    return resul

def empaquetar_azar(E, L, Lim):
    resul = None
    E = list(E)

    for x in range(Lim):
        random.shuffle(E)

        nueva = empaquetar_ordenado(E, L, False)
        if resul is None or len(nueva) < len(resul):
            resul = nueva

    return resul

def main():
    elementos = [random.randint(0, 500000) for x in range(1000)]
    L = 500000 * 2

    ordenados = empaquetar_ordenado(list(elementos), L)
    print("Ordenados: ", len(ordenados))

    azar = empaquetar_azar(list(elementos), L, 200)
    print("Azar: ", len(azar))

if __name__ == '__main__':
    main()