问如何为n个人找到最优的汽车数量？

EN

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>