如何找到适合n个人的最佳汽车数量？

Question

有一组车

{
 3: 1
 4: 1.4
 8: 2.2
}

其中键是汽车容量，值是价格系数。

对于人数较多的情况，应寻找一套汽车，并且价格系数之和应尽可能低。例如，对于 7 人来说，使用一辆容量 = 8 的汽车是合理的。对于 9 人来说，使用一辆 8 容量的汽车就可以了。和 1 个 3 帽。汽车。

形成最佳汽车组的算法是什么？实际使用中的容量和系数可能有所不同，因此请勿依赖此处给出的数据。谢谢！

UPD。这是一段构建没有效率系数的汽车组的代码/希望可能的汽车变体不要估计 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>

时间复杂度

如果没有重复模式优化，则运行时间为O（人 * 汽车）。当包含该优化时，它以O(LCM(seats) * cars)运行，变得独立于人数。