Найдите наилучшую комбинацию из заданного множества множеств

Скажем, у вас есть груз. Он должен пройти от точки А до точки Б, от точки Б до точки C и, наконец, от точки C до точки D. вам нужно добраться туда за пять дней за наименьшую сумму денег. Есть три возможных грузоотправителя для каждой ноги, каждый со своим собственным различным временем и стоимостью для каждой ноги:

Array
(
    [leg0] => Array
        (
            [UPS] => Array
                (
                    [days] => 1
                    [cost] => 5000
                )

            [FedEx] => Array
                (
                    [days] => 2
                    [cost] => 3000
                )

            [Conway] => Array
                (
                    [days] => 5
                    [cost] => 1000
                )

        )

    [leg1] => Array
        (
            [UPS] => Array
                (
                    [days] => 1
                    [cost] => 3000
                )

            [FedEx] => Array
                (
                    [days] => 2
                    [cost] => 3000
                )

            [Conway] => Array
                (
                    [days] => 3
                    [cost] => 1000
                )

        )

    [leg2] => Array
        (
            [UPS] => Array
                (
                    [days] => 1
                    [cost] => 4000
                )

            [FedEx] => Array
                (
                    [days] => 1
                    [cost] => 3000
                )

            [Conway] => Array
                (
                    [days] => 2
                    [cost] => 5000
                )

        )

)

Как вы собираетесь найти лучшую комбинацию программно?

Моя лучшая попытка до сих пор (третий или четвертый алгоритм) :

1. Найдите самый длинный грузоотправитель для каждой ноги
2. Устранить большинство "expensive" один
3. Найти самый дешевый грузоотправитель для каждой ноги
4. Рассчитайте общую стоимость & дней
5. Если дни приемлемы, закончите, иначе, Гото 1

Быстро высмеивается в PHP (обратите внимание, что тестовый массив ниже работает плавно, но если вы попробуете его с тестовым массивом сверху, он не найдет правильную комбинацию):

$shippers["leg1"] = array(
    "UPS"    => array("days" => 1, "cost" => 4000),
    "Conway" => array("days" => 3, "cost" => 3200),
    "FedEx"  => array("days" => 8, "cost" => 1000)
);

$shippers["leg2"] = array(
    "UPS"    => array("days" => 1, "cost" => 3500),
    "Conway" => array("days" => 2, "cost" => 2800),
    "FedEx"  => array("days" => 4, "cost" => 900)
);

$shippers["leg3"] = array(
    "UPS"    => array("days" => 1, "cost" => 3500),
    "Conway" => array("days" => 2, "cost" => 2800),
    "FedEx"  => array("days" => 4, "cost" => 900)
);    

$times = 0;
$totalDays = 9999999;

print "<h1>Shippers to Choose From:</h1><pre>";
print_r($shippers);
print "</pre><br />";

while($totalDays > $maxDays && $times < 500){
            $totalDays = 0;
            $times++;
            $worstShipper = null;
            $longestShippers = null;
            $cheapestShippers = null;

            foreach($shippers as $legName => $leg){
                //find longest shipment for each leg (in terms of days)
                unset($longestShippers[$legName]);
                $longestDays = null;        

                if(count($leg) > 1){
                    foreach($leg as $shipperName => $shipper){
                        if(empty($longestDays) || $shipper["days"] > $longestDays){
                            $longestShippers[$legName]["days"] = $shipper["days"];
                            $longestShippers[$legName]["cost"] = $shipper["cost"];
                            $longestShippers[$legName]["name"] = $shipperName;
                            $longestDays = $shipper["days"];
                        }
                    }           
                }
            }

            foreach($longestShippers as $leg => $shipper){
                $shipper["totalCost"] = $shipper["days"] * $shipper["cost"];

                //print $shipper["totalCost"] . " &lt;?&gt; " . $worstShipper["totalCost"] . ";";

                if(empty($worstShipper) || $shipper["totalCost"] > $worstShipper["totalCost"]){
                    $worstShipper = $shipper;
                    $worstShipperLeg = $leg;
                }
            }

            //print "worst shipper is: shippers[$worstShipperLeg][{$worstShipper['name']}]" . $shippers[$worstShipperLeg][$worstShipper["name"]]["days"];
            unset($shippers[$worstShipperLeg][$worstShipper["name"]]);

            print "<h1>Next:</h1><pre>";
            print_r($shippers);
            print "</pre><br />";

            foreach($shippers as $legName => $leg){
                //find cheapest shipment for each leg (in terms of cost)
                unset($cheapestShippers[$legName]);
                $lowestCost = null;

                foreach($leg as $shipperName => $shipper){
                    if(empty($lowestCost) || $shipper["cost"] < $lowestCost){
                        $cheapestShippers[$legName]["days"] = $shipper["days"];
                        $cheapestShippers[$legName]["cost"] = $shipper["cost"];
                        $cheapestShippers[$legName]["name"] = $shipperName;
                        $lowestCost = $shipper["cost"];
                    }
                }

                //recalculate days and see if we are under max days...
                $totalDays += $cheapestShippers[$legName]['days'];  
            }
            //print "<h2>totalDays: $totalDays</h2>";
        }

        print "<h1>Chosen Shippers:</h1><pre>";
        print_r($cheapestShippers);
        print "</pre>";

Я думаю, что мне, возможно, придется на самом деле сделать что-то вроде того, где я буквально делаю каждую комбинацию по одному (с серией петель) и складываю общее "score" каждого и нахожу лучший....

EDIT: Чтобы уточнить, это не задание "homework" (я не в школе). Это часть моего текущего проекта на работе.

Требования (как всегда) постоянно менялись. Если бы мне дали текущие ограничения в то время, когда я начал работать над этой проблемой, я бы использовал какой-то вариант алгоритма A* (или Dijkstra'S, или shortest path, или simplex, или что-то еще). Но все менялось и менялось, и это привело меня туда, где я сейчас нахожусь.

Поэтому я думаю, что это означает, что мне нужно забыть обо всем дерьме, которое я сделал до этого момента, и просто пойти с тем, что я знаю, что должен идти, что является алгоритмом поиска пути.