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

Question

There is a set of cars

{
 3: 1
 4: 1.4
 8: 2.2
}

where the key is the capacity of the car, and the value is the price coefficient.

For a number of people, we must find a set of cars, and the sum of price factors should be as small as possible. For example, for 7 people it is reasonable to use one car with power = 8. And for 9 people it is normal to have one 8-cap. and one 3-cap. cars.

What algorithm will form the optimal set of cars? Capacities and ratios may vary in actual use, so it’s important not to rely on the data provided here. Thank!

UPD. Here is a piece of sets of code building cars without efficiency / hope for possible car options is not evaluated 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;

Answer 1

:

, , . , .

, , , . , . , .

: ( ) , . , , , "" , , . , . , , , (1 2...). . 3, 4 8 . LCM - 24. , 24 : 48 , 72,... .. ( , , , = LCM)

DP " " " ". , , ,... .., , , :

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):
<input id="inpCars" value='{ "3": 1, "4": 1.4, "8": 2.2 }' style="width:100%"><p>
People: <input id="inpPeople" type="number" value="13" min="0" style="width:6em"><p>
Optimal Car Assignment (lowest price):
<pre id="preOut"></pre>

Hide result

O (people * cars). , O (LCM (seat) *), .

Answer 2

, Knapsack. /. , . , : https://www.geeksforgeeks.org/knapsack-problem/