脚本
具有以下特性的可用车辆列表:
车辆{乘客:4,行李:2,行李箱:8}
车辆2{乘客:5,行李:3,行李箱:10}
车辆3{乘客:6,行李:3,行李箱:10}
车辆4{乘客:8,行李:4,行李箱:10}
现在,如果用户要求旅行(13名乘客,6件行李,15个行李箱),那么最有效的车辆结果将是:
车辆2+车辆4
问题定义:
我已经开发了一个流量/算法(但仅限于乘客计数),但当乘客/行李箱/行李数量超过3辆或更多车辆的需求时,我无法开发算法。
代码:
function ajax_getVehicles() {
$vehicleType = $_POST['vehicle_type'];
$passengers = intval($_POST['passengers']);
$luggage = intval($_POST['luggage']);
$suitcases = intval($_POST['suitcases']);
$requiredVehicles = array();
// 1. Check if all passengers fit in a single car
if (!$requiredVehicles) {
$vehicle = $this->common_model->get_where('fleets', array('vehicle_type' => $vehicleType, 'passengers >=' => $passengers), 'passengers ASC');
if ($vehicle)
array_push($requiredVehicles, $vehicle[0]);
}
// 2. Try sending duplicate vehicles
$vehicles = $this->common_model->get_where('fleets', array('vehicle_type' => $vehicleType), 'passengers ASC');
if (!$requiredVehicles) {
foreach ($vehicles as $v) {
if ($v['passengers'] * 2 == $passengers) {
array_push($requiredVehicles, $v, $v);
}
}
}
// 3. Find best possible solution
if (!$requiredVehicles) {
$totalPermutation = gmp_fact(count($vehicles)) / (gmp_fact(count($vehicles) - 2) * gmp_fact(2));
$total_pax_array = array();
for ($i = 0; $i < $totalPermutation; $i++) {
for ($count = $i + 1; $count < count($vehicles); $count++) {
$total_pax = $vehicles[$i]['passengers'] + $vehicles[$count]['passengers'];
if ($total_pax >= $passengers) {
if (count($total_pax_array) < 1) {
$requiredVehicles = array($vehicles[$i], $vehicles[$count]);
} else if ($total_pax < min($total_pax_array)) {
$requiredVehicles = array($vehicles[$i], $vehicles[$count]);
}
array_push($total_pax_array, $total_pax);
}
}
}
}
// 4. check if requirement can be acheived by sending duplicate vehicles
if (!$requiredVehicles) {
foreach ($vehicles as $v) {
if ($v['passengers'] * 2 > $passengers) {
array_push($requiredVehicles, $v, $v);
}
}
}
if (!$requiredVehicles)
jsonOutput('ERROR', 'call for 3 vehicles required.');
else
jsonOutput('SUCCESS', 'criteria matching vehicles', $requiredVehicles);
}
最佳答案
这可以通过以下递归公式使用Dynamic Programming (DP)来解决:
D(p,l,s,0) = infinity if p>0 or l>0 or s>0
0 otherwise
D(p,l,s,i) = min { D(p,l,s,i-1), D(p-cars[i].passangers, l-cars[i].luggage, s-cars[i].suitcases) + 1}
其思想是d(p,l,s,i)表示1,2,3…车厢之间的最小车厢数,i-可乘坐
p
乘客,l
行李和s
行李箱。时间复杂度(如果应用DP技术):
O(n*p*l*s)
,其中n
是可用汽车的数量,p
所需的乘客数,l
所需的行李数,以及s
所需的行李箱数。另一种解决方案是生成cars的所有子集,检查每个子集是否是可行解,并从可行解中选择最小大小的子集。时间复杂度:
O(2^n)
关于php - 寻找最佳解决方案所需的算法逻辑,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/31852684/