массив, распределение суммы как можно более равномерно
Вариант решения ниже, не очень оптимальный, подскажите любое другое решение.
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>
|
| Часовой пояс GMT +3, время: 12:58. |