Calculating weighted values as integers for layout

Question

I have a layout in which:

• The page is broken up into as many fixed width columns as can fit across it.
• Rows of boxes fit across these columns, each spanning a whole number of columns.
• Boxes each have a weight used to determine their column span (IE: if a row has 6 columns and 2 boxes with weights 1 and 2, the boxes will have column spans of 2 and 4 respectively).

If fractional column spans were allowed, this would be simple (multiply each weight by the column count and divide by the total weight) but breaking it into integers turns out to be waaaay more difficult. This is what I've come up with:

function weightedIntegerValues(weights, total) {
    const totalWeight = totalValues(weights);
    const weightedValues = weights.map(weight => Math.round(total * weight / totalWeight));

    for (let totalValue = totalValues(weightedValues); totalValue > total; totalValue = totalValues(weightedValues))
        subtractOneFromHighest(weightedValues);

    return weightedValues;
}

For brevity I've omitted the following functions:

• totalValues - gets the sum of all values in an array
• subtractOneFromHighest - finds the highest value in an array and subtracts 1 from it (modifies array in place)

The function works like this:

1. Calculates the weighted values as described above, but rounds each value as it progresses
2. Continually subtracts 1 from the highest value in weightedValues until the sum of weightedValues is less than or equal to total (accounting for any pairs of 0.5s that were rounded up)

This function has 2 major problems:

1. It's horribly inefficient (both totalValues and subtractOneFromHighest have to loop through the array inside of the function's main loop)
2. It incorrectly favors reducing the first "highest value" it finds.

To illustrate point (2) consider the following:

weightedIntegerValues([1, 2, 4, 3], 5); // [1, 1, 1, 2]

The weighting function found rounded values of [1, 1, 2, 2], determined that was greater than the desired total of 5 and subtracted 1 from the first highest value it found (at index 3), but really we would have liked to subtract 1 from index 4, which was 1.5 before rounding, giving us [1, 1, 2, 1].

My questions are as follows:

1. Can this be done in better than N²? It'd be great to get it down to N.
2. Is there some simple, and more mathematical way to favor numbers that were rounded to 0.5 instead of favoring lefter or righter values?
3. Is there some neato CSS that could handle this use-case for me? Flex-box comes pretty close, but hasn't quite lined up for me, yet (this is probably an entire other question on its own).

Answer 1

Here's a way to achieve this vaguely based on this answer:

function weightedIntegerValues(weights, total) {
    let flooredValues = [];
    const weightSum = weights.reduce((sum, item) => {
        return sum + valueFunc(item);
    }, 0);

    let flooredSum = 0

    weights.forEach((weight, i) => {
        const weighted = total * weight / weightSum
        const floored = Math.floor(weighted);

        flooredValues.push({
            floored: floored,
            diff: weighted - floored,
            index: i
        });

        flooredSum = flooredSum + flooredValues[i].floored;
    });

    flooredValues = flooredValues.sort((a, b) => b.diff - a.diff);

    const difference = total - flooredSum;

    for (let i = 0; i < difference; i++) {
        flooredValues[i].floored += 1;
    }

    return flooredValues.sort((a, b) => a.index - b.index).map(v => v.floored);
}