массив, распределение суммы как можно более равномерно
Вариант решения ниже, не очень оптимальный, подскажите любое другое решение.
var input = [5,10,0,12], //массив лимита каждой ячейки
total = 7, // сумма которую надо распределить равномерно
output = [];// результат распределения
//total = 7 => output = [2,2,0,3]
//total = 20 => output = [5,7,0,8]
//total = 40 => output = [5,10,0,12]
function fn(input, total, output) {
for (var i = 0; total; i = ++i % input.length) {
output[i] = output[i] || 0;
if (output[i] + 1 > input[i]) continue;
output[i]++;
total--
}
return output
};
console.log(fn(input, total, output))//[3, 2, 0, 2]
|
Ровнее только с плавающей точкой.
|
j0hnik,
все числа целые, требуется оптимизация, желательно 1 проход по массиву или 2 - 3, а не как сейчас, пока сумма по 1 не уменьшится до конца. |
j0hnik,
что-то типа output[i] = Math.floor(total/input.length) |
function fn(input, total) {
const output = [];
const order = input.map((_, index) => index);
const sortedOrder = order.sort((a, b) => input[b] - input[a]);
const mustCheckIndexes = [];
for (let i = 0; i < sortedOrder.length; i++) {
const sortedIndex = sortedOrder[i];
if (i === 0) {
mustCheckIndexes.push(sortedIndex);
} else if (input[sortedIndex] === input[sortedOrder[i - 1]]) mustCheckIndexes.push(sortedIndex);
else break;
}
for (let i = 0; total; i = ++i % input.length) {
let breakCycle = false;
for (const mustCheckIndex of mustCheckIndexes) {
if (output[mustCheckIndex] === input[mustCheckIndex]) breakCycle = true;
else breakCycle = false;
}
if (breakCycle) break;
const currIndex = sortedOrder[i];
output[currIndex] = output[currIndex] || 0;
if (output[currIndex] + 1 > input[currIndex]) {
continue;
}
output[currIndex]++;
total--
}
return output
};
|
рони,
придумал разве что проверку добавить if(input.reduce((c,e)=> e+c) <= total) return output = [...input]; больше ничего. |
EmperioAf,
спасибо, попробую разобраться :thanks: j0hnik, Rise, спасибо, да я в курсе когда total больше суммы -- выше был минимальный пример. |
Цитата:
var input = [5,10,0,12], //массив лимита каждой ячейки
total = 7, // сумма которую надо распределить равномерно
output = [];// результат распределения
//total = 7 => output = [2,2,0,3]
//total = 20 => output = [5,7,0,8]
//total = 40 => output = [5,10,0,12]
function allocate(input, total, output) {
var rest = total; //остаток
var quotient = Math.ceil(total/input.length); //частное
var waste_count = 0; //счётчик превышений
for( var i = 0; i < input.length; i++ ){
output[i] = output[i] || 0;
output[i] += quotient;
rest -= quotient;
if( output[i] > input[i] ) {
var waste = output[i] - input[i];
output[i] -= waste;
rest += waste;
waste_count++;
}
if( rest <= 0 ) {
output[i] += rest;
break;
}
}
//console.log(waste_count, rest, quotient);
if( waste_count == input.length ) return output;
if( rest > 0 ) return allocate(input, rest, output);
return output;
}
console.log( allocate(input, 7, []) );
console.log( allocate(input, 20, []) );
console.log( allocate(input, 40, []) );
|
Белый шум,
спасибо! |
равномерное распределение суммы
:write: вариант на котором остановился, если есть замечания напишите, всем откликнушимся большое спасибо!!! :thanks:
<script>
function allocate(input, total) {
const output = [];
const length = input.length;
const order = input.map((value, index) => ({value,index}));
const sortedOrder = order.sort((a, b) => a.value - b.value);
for (let i = 0; i < length; i++) {
let {value,index} = sortedOrder[i];
let num = Math.floor(total/(length - i))
if(num > value) num = value;
total -= num;
output[index] = num
}
return output
};
let input = [5,10,0,12];
for (let total = 0; total < 41; total++) {
let output = allocate(input, total)
document.write(`${total}=>${output}<br>`)
}
</script>
|
Цитата:
|
Alexandroppolus,
Максимум можно получить с помощью Math.max(), но чем это поможет - что-то не вдупляю. рони, Проход хоть и один, но для каждого элемента массива выполняется деление - сложная операция, по идее. Хотя я хз как там процессоры внутри работают, может им это и проще чем пару лишних проходов сделать. |
Alexandroppolus,
Цитата:
Цитата:
max = sortedOrder.slice(-1)[0].valueи как это использовать? |
рони,
я про тот "максимум", который можно отсыпать в output[i] вот, изобразил слова в г-коде. Идея в принципе та же, но нет деления на каждой итерации (есть только целочисленное умножение), и дополнительной памяти только массив целых чисел, а не массив объектов. Не знаю, насколько это сможет ускорить, проверять было лень :)
function allocate(input, total) {
var output = [];
var length = input.length;
var sortedInput = input.slice().sort(function (a, b) { return a - b; });
var lastValue = 0;
var maxH = 0;
var remainder = 0;
for (var i = 0; total > 0 && i < length; ++i) {
var item = sortedInput[i];
var height = item - lastValue;
if (height > 0) {
lastValue = item;
var width = length - i;
var area = width * height;
if (total < area) {
height = Math.floor(total / width);
remainder = total % width;
}
maxH += height;
total -= area;
}
}
for (var i = 0; i < length; ++i) {
var item = input[i];
output.push(item > maxH ? maxH + (--remainder >= 0 ? 1 : 0) : item);
}
return output
}
// проверка для разных total
var input = [5,10,0,12, 7, 3];
for (var total = 0; total < 41; total++) {
var output = allocate(input, total);
console.log(`${total} => ${output}`);
}
см. консоль |
Alexandroppolus,
:thanks: |
| Часовой пояс GMT +3, время: 03:26. |