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

Скажем, у вас есть посылка. Он должен пройти из точки A в точку B, из точки B в точку 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. Устраните самый «дорогой»
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>";

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

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

Требования (как всегда) постоянно меняются. Если бы мне дали текущие ограничения в то время, когда я начал работать над этой проблемой, я бы использовал какой-нибудь вариант алгоритма A * (или алгоритм Дейкстры, или кратчайший путь, или симплекс, или что-то в этом роде). Но все трансформировалось и менялось, и это подводит меня к тому месту, где я сейчас нахожусь.

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