Скажите, что у вас есть отгрузка. Ему нужно перейти от точки А до точки В, точки В до точки С и, наконец, точки С до точки 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
Быстро издевались вверх в 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"] . " <?> " . $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>";
Я думаю, Мне, возможно, придется на самом деле делать что-то вроде того, где я буквально делаю каждую комбинацию один за другим (с серией циклов) и складываю общий «счет» каждого из них и нахожу лучший ...
EDIT: Чтобы уточнить, это не задание «домашнее задание» (я не в школе). Это часть моего текущего проекта на работе.
Требования (как всегда) постоянно меняются. Если бы мне дали текущие ограничения в то время, когда я начал работать над этой проблемой, я бы использовал некоторый вариант алгоритма A * (или Dijkstra, или самый короткий путь или симплекс или что-то еще). Но все изменилось и изменилось, и это привело меня туда, где я сейчас.
Так что, я думаю, это означает, что мне нужно забыть обо всем, что я сделал с этим моментом, и просто пойти с тем, что, как я знаю, должен пойти, это алгоритм поиска путей.
+1 для приближающихся требований к морфингам с течением времени с «давайте отбросить это дерьмо и начать все». – Alex 2012-07-03 15:12:50