How to find the optimal quantity of cars for n of people?

Question

There is a set of cars

{
 3: 1
 4: 1.4
 8: 2.2
}

where the key is a car capacity and the value is a price coefficient.

For a number of people we should find a set of cars and the sum of price coefficients should be as low as possible. For example, for 7 people it's reasonable to use one car with capacity = 8. And for 9 people it's fine to have one 8-cap. and one 3-cap. cars.

What's the algorithm to form the optimal set of cars? The capacities and coefficients may be different in real use so it's important no to rely on the data given here. Thanks!

UPD. Here's a piece of code building sets of cars without efficiency factor/hoping for possible car variants do not estimate 3:

let carSet = {},
    peopleFree = 123456,
    cars =
        [
            {capacity: 3, coefficient: 1},
            {capacity: 4, coefficient: 1.4},
            {capacity: 3, coefficient: 2.2},
        ],
    minCapacity = 0,
    maxCapacity = 0;

_.forEach(cars, (car) => {
    if (car['capacity'] >= maxCapacity) {   //find max capacity
        maxCapacity = car['capacity'];
    }

    if (car['capacity'] <= maxCapacity) {   //find min capacity
        minCapacity = car['capacity'];
    }

    carSet[car['capacity']] = 0;            //create available set of capacities
});

_.forEach(cars, (car) => {

    if (peopleFree <= 0)    //all people are assigned. stopping here
        return;

    if (peopleFree <= minCapacity) {    //if people quantity left are equal to the min car, we assign them
        carSet[minCapacity] += 1;
        peopleFree = 0;
        return;
    }

    let currentCapacityCars = Math.floor(peopleFree / car['capacity']);

    peopleFree = peopleFree % car['capacity'];
    carSet[car['capacity']] = currentCapacityCars;

    if (peopleFree && car['capacity'] == minCapacity) {
        carSet[minCapacity] += 1;
    }
});
return carSet;

trincot · Accepted Answer

You could use a Dynamic Programming technique:

For a given number of people, see if the best solution for one person less yields an empty seat. If so, that configuration is also the best for one more person.

If not, pick a car, seat as many people in it as possible, and see what the best solution is for the remaining number of people. Combine the total price of that best solution with the one for the chosen car. Repeat this for all types of cars and take the one the yields the lowest price.

There is another optimisation possible: when creating long series (of allocations for an increasing number of people), a pattern starts to emerge that repeats over and over again. So when the number of people is large, we could use the result for a small number of people, at the same "offset" in the pattern and then add the number of cars that is the constant difference between two subsequent pattern-blocks. My impression is that a repeating pattern is guaranteed when the least common multiple of the number of seats is reached. We should take the second block of this pattern, since the first one is distorted by the fact that we cannot fill a car when we only have a few people (1 or 2...). This situation will not repeat. Take the example of cars with 3, 4 and 8 seats. The LCM is 24. There is a guaranteed pattern that will start to repeat from 24 people onward: it repeats at 48 people, 72, ...etc. (It may repeat more often, but at least it repeats with blocks of size = LCM)

You can implement the DP algorithm with a top-down or bottom-up approach. I have here implemented it in bottom-up, starting with calculating the best solution for one person, for two persons, ...etc, until the required number of people is achieved, always keeping all the previous results so they do not need to be calculated twice:

function minimize(cars, people) {
    // Convert cars object into array of objects to facilitate rest of code
    cars = Object.entries(cars)
            .map(([seats, price]) => ({ seats: +seats, price }));
    // Calculate Least Common Multiple of the number of seats:
    const chunk = lcm(...cars.map( ({seats}) => seats ));
    // Create array that will have the DP best result for an increasing
    // number of people (index in the array).
    const memo = [{
        carCounts: Array(cars.length).fill(0),
        price: 0,
        freeSeats: 0
    }];
    // Use DP technique to find best solution for more and more people,
    //   but stop when we have found all results for the repeating pattern.
    for (let i = 1, until = Math.min(chunk*2, people); i <= until; i++) {
        if (memo[i-1].freeSeats) { 
            // Use same configuration as there is still a seat available
            memo[i] = Object.assign({}, memo[i-1]);
            memo[i].freeSeats--;
        } else {
            // Choose a car, place as many as possible people in it,
            //    and see what the best solution is for the remaining people.
            // Then see which car choice gives best result.
            const best = cars.reduce( (best, car, seq) => {
                const other = memo[Math.max(0, i - car.seats)],
                    price = car.price + other.price;
                return price < best.price ? { price, car, other, seq } : best;
            }, { price: Infinity } );
            memo[i] = {
                carCounts: best.other.carCounts.slice(),
                price: best.price,
                freeSeats: best.other.freeSeats + Math.max(0, best.car.seats - i)
            };
            memo[i].carCounts[best.seq]++;
        }
    }
    let result;
    if (people > 2 * chunk) { // Use the fact that there is a repeating pattern
        const times = Math.floor(people / chunk) - 1;
        // Take the solution from the second chunk and add the difference in counts
        //   when one more chunk of people are added, multiplied by the number of chunks:
        result = memo[chunk + people % chunk].carCounts.map( (count, seq) =>
            count + times * (memo[2*chunk].carCounts[seq] - memo[chunk].carCounts[seq])
        );
    } else {
         result = memo[people].carCounts;
    }
    // Format result in Object key/value pairs:
    return Object.assign(...result
                            .map( (count, seq) => ({ [cars[seq].seats]: count })));
}

function lcm(a, b, ...args) {
    return b === undefined ? a : lcm(a * b / gcd(a, b), ...args);
}

function gcd(a, b, ...args) {
    if (b === undefined) return a;
    while (a) {
        [b, a] = [a, b % a];
    }
    return gcd(b, ...args);
}

// I/O management
function processInput() {
    let cars;
    try {
        cars = JSON.parse(inpCars.value);
    } catch(e) {
        preOut.textContent = 'Invalid JSON';
        return;
    }
    const result = minimize(cars, +inpPeople.value);
    preOut.textContent = JSON.stringify(result);
}

inpPeople.oninput = inpCars.oninput = processInput;
processInput();

Car definition (enter as JSON):

People: 

Optimal Car Assignment (lowest price):

Time Complexity

Without the repeating-pattern optimisation, this runs in O(people * cars) time. When that optimisation is included, it runs in O(LCM(seats) * cars), becoming independent of the number of people.

How to find the optimal quantity of cars for n of people?

Answers (2)

Time Complexity

Related Questions