PrEDA: distribuir cosas con volumen en el mínimo de paquetes disponibles

Hoy traigo de nuevo otro code-cata, para resolver el clásico problema de llenar paquetes con cosas de volumen variable, usando el mínimo de paquetes posible. Este problema de igual modo que los anteriores, se podría resolver de varias formas. Pero la forma más eficiente es usar el algoritmo de ramificación y poda.

El algoritmo de ramificación y poda, mediante este refinamiento, es una variante del de vuelta atrás. Como es habitual comenzamos generando todas las posibles soluciones como si lo resolviéramos por fuerza bruta. Generando un árbol de soluciones, haciendo la misma vuelta atrás para las soluciones no posibles. Es decir, haremos vuelta atrás si ya no caben más cosas en el paquete que estemos llenando; ramificando llenando la siguiente cosa en el siguiente paquete. También haremos vuelta atrás si hemos hecho un llenado completo con todas las cosas, para continuar estudiando la siguiente ramificación posible.

Ahora bien, aquí viene la ramificación y poda. Llevaremos cuenta de una cota que nos indicará el coste en paquetes de la mejor solución hasta ahora encontrada. De esta forma, si la estimación mejor de una ramificación no puede mejorar la cota, directamente podamos. Además, si en una ramificación, su estimación peor es mejor que la cota, actualizamos la cota para conseguir llegar a dicha solución.

Inicializando los datos

<?php

define('NUMBER_OF_THINGS', 7);
define('NUMBER_OF_PACKAGES', 7);
define('MAX_VOLUME', 9);
$thingsVolume = array();
$packagingCapacity = array();
$solutionThingsPackage = array();
$GLOBALS['betterSolution'] = array();
for ($i = 0; $i < NUMBER_OF_THINGS; ++$i) {
    $thingsVolume[$i] = rand(1, MAX_VOLUME);
    $packagingCapacity[$i] = MAX_VOLUME;
    $solutionThingsPackage[$i] = $GLOBALS['betterSolution'][$i] = '#';
}
echo '########################################################################################'.PHP_EOL
    .'Things volume: '.implode('-', $thingsVolume).PHP_EOL
    .' packaging capacity: '.implode('-', $packagingCapacity).PHP_EOL
    .' things package: '.implode('-', $solutionThingsPackage).PHP_EOL
    .' initial optimistic estimation: '.optimisticEstimation($solutionThingsPackage).PHP_EOL
    .' initial pessimistic estimation: '.pessimisticEstimation(
        $solutionThingsPackage, $packagingCapacity, $thingsVolume)
    .PHP_EOL
    .PHP_EOL;
$GLOBALS['cota'] = pessimisticEstimation($solutionThingsPackage, $packagingCapacity, $thingsVolume);

Un ejemplo de salida de datos por pantalla podría ser así:

########################################################################################
Things volume: 9-4-4-1-3-3-2
 packaging capacity: 9-9-9-9-9-9-9
 things package: #-#-#-#-#-#-#
 initial optimistic estimation: 0
 initial pessimistic estimation: 7

El resto del código

Para explorar el árbol de soluciones, el algoritmo original usa un montículo para convertirlo en iterativo. Aquí esta solución es recursiva y así evitamos tener que implementar un montículo. A este algoritmo le falta esto, que mejoraría el rendimiento, porque así iríamos probando las siguientes ramificaciones empezando por las mejor estimadas, haciendo así una mejor poda. Yo así lo dejo, si lo necesitas mejorado dale.. 😉

minimizeAmountOfPackaging($solutionThingsPackage, $packagingCapacity, $thingsVolume, 0);

echo PHP_EOL.PHP_EOL.'FINALLY BETTER SOLUTION: '.implode('-', $GLOBALS['betterSolution']).PHP_EOL
    .'Using '.solutionCost($GLOBALS['betterSolution']).' packages from a total of '.NUMBER_OF_PACKAGES.' packages.'.PHP_EOL;

function minimizeAmountOfPackaging($solutionThingsPackage, $packagingCapacity, $thingsVolume, $k)
{
    echo PHP_EOL.'==>> packing object with $k = '.$k.PHP_EOL
        .'Things vol.: '.implode('-', $thingsVolume)
        .' capacities: '.implode('-', $packagingCapacity)
        .' packaging: '.implode('-', $solutionThingsPackage)
        .PHP_EOL;

    for ($package = 0; $package < NUMBER_OF_PACKAGES; ++$package) {
        echo ' $package = '.$package
            .' cota = '.$GLOBALS['cota']
            .' better = '.implode('-', $GLOBALS['betterSolution'])
            .PHP_EOL;

        if ($thingsVolume[$k] <= $packagingCapacity[$package]) {
            $solutionThingsPackage[$k] = $package;
            $packagingCapacity[$package] -= $thingsVolume[$k];

            echo ' trying with: things vol.: '.implode('-', $thingsVolume)
                .' capacities: '.implode('-', $packagingCapacity)
                .' packaging: '.implode('-', $solutionThingsPackage)
                .' optim = '.optimisticEstimation($solutionThingsPackage)
                .' pessim = '.pessimisticEstimation(
                    $solutionThingsPackage, $packagingCapacity, $thingsVolume)
                .' cota = '.$GLOBALS['cota']
                .' better = '.implode('-', $GLOBALS['betterSolution'])
                .PHP_EOL;

            if (isSolution($solutionThingsPackage)) {
                if (solutionCost($solutionThingsPackage) <= $GLOBALS['cota']) {
                    echo ' POSSIBLE SOLUTION: '.implode('-', $solutionThingsPackage).PHP_EOL;
                    $GLOBALS['cota'] = solutionCost($solutionThingsPackage);
                    $GLOBALS['betterSolution'] = $solutionThingsPackage;
                    break 1;
                }
            } else {
                if (optimisticEstimation($solutionThingsPackage) <= $GLOBALS['cota']) {
                    if ($k + 1 < NUMBER_OF_THINGS
                    and pessimisticEstimation($solutionThingsPackage, $packagingCapacity, $thingsVolume) 
                    <= $GLOBALS['cota']) {
                        minimizeAmountOfPackaging(
                            $solutionThingsPackage, $packagingCapacity, $thingsVolume, $k + 1
                        );
                    }
                    if (pessimisticEstimation($solutionThingsPackage, $packagingCapacity, $thingsVolume) 
                    < $GLOBALS['cota']) {
                        $GLOBALS['cota'] = pessimisticEstimation(
                            $solutionThingsPackage, $packagingCapacity, $thingsVolume
                        );
                    }
                }
            }

            $solutionThingsPackage[$k] = '#';
            $packagingCapacity[$package] += $thingsVolume[$k];
        }
    }
}

function isSolution($solutionThingsPackage)
{
    for ($i = 0; $i < NUMBER_OF_THINGS; ++$i) {
        if ($solutionThingsPackage[$i][0] == '#') {
            return false;
        }
    }

    return true;
}

function solutionCost($solutionThingsPackage)
{
    return optimisticEstimation($solutionThingsPackage);
}

function pessimisticEstimation($solutionThingsPackage, $packagingCapacity, $thingsVolume)
{
    $numberOfUsedPackaging = optimisticEstimation($solutionThingsPackage);
    $numberOfNotPackagedThings = 0;

    for ($i = 0; $i < NUMBER_OF_THINGS; ++$i) {
        if ($solutionThingsPackage[$i][0] == '#') {
            ++$numberOfNotPackagedThings;
        }
    }

    return $numberOfUsedPackaging + $numberOfNotPackagedThings;
}

function optimisticEstimation($solutionThingsPackage)
{
    $usedPackaging = array();

    for ($i = 0; $i < NUMBER_OF_THINGS; ++$i) {
        if ($solutionThingsPackage[$i][0] != '#') {
            $usedPackaging[$solutionThingsPackage[$i]] = 'used';
        }
    }

    return count($usedPackaging);
}

Lo puedes grabar en un fichero .php y al ejecutarlo tienes que ver algo parecido a esto: