Algorithm Logic Required for finding best solution

Question

Scenario

List of vehicles available with following properties:

vehicle1 {passengers: 4, luggages: 2, suitcases: 8}

vehicle2 {passengers: 5, luggages: 3, suitcases: 10}

vehicle3 {passengers: 6, luggages: 3, suitcases: 10}

vehicle4 {passengers: 8, luggages: 4, suitcases: 10}
Now if, the user demands for a journey with (13 passengers, 6 luggage, 15 suitcases), then the best efficient vehicle result will be:

vehicle2 + vehicle4

Problem Definition: I've been able to develop a flow/algorithm upto this (but only with passengers count), but when the passengers/suitcase/luggage quantity exceeds with a demand of 3 vehicles or more I'm not being able to develop the algorithm for it.

Code:

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);
}

amit · Accepted Answer · 2015-08-06 10:24:13Z

4

This can be solved using Dynamic Programming (DP) by following the recursive formula:

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}

The idea is D(p,l,s,i) represents the minimal number of cars between the cars 1,2,3...,i - that can take p passengers, l luggages and s suitcases.

Time complexity (if applying DP techniques): O(n*p*l*s), where n is the number of available cars, p required number of passengers, l - required number of luggages, and s - required number of suitcases.

An alternative solution is to generate all subsets of cars, for each subset check if it's a feasible solution, and chose the minimal size subset out of the feasible solutions. Time complexity: O(2^n)

answered Aug 6, 2015 at 10:24

amit

179k27 gold badges245 silver badges348 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

TheManish Over a year ago

Thank you for replying @amit. I'm totally unknown about Dynamic Programming. Can you refer me some other similar solutions matching this criteria. If possible?

amit Over a year ago

@ManishShrestha DP Is pretty simple, the easiest form is memoization, which basically means - you don't need to recalculate things twice because you "remember" the value. Have a look at the wikipedia page I linked for more details. I also offered a brute force option to solve it optimally.

TheManish Over a year ago

Alright. I'll try figuring out DP, & will ping back here. Thank you once again @amit.

Collectives™ on Stack Overflow

Algorithm Logic Required for finding best solution

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related