Добрый день. Наткнулся в инете на интересную задачку. Интересно, сможет кто-нить ее решить более оптимально. Суть задачи: в супермаркете стоит очередь к кассам самообслуживания. Ваша задача - написать функцию для расчета общего времени, необходимого для обслуживания всех клиентов!
МассивПокупателей: массив положительных целых чисел, представляющих очередь. Каждое целое число представляет клиента,и его значение - это количество времени, которое ему требуется для обслуживания.
Покупатели подходят к кассам в порядке очереди от первого элемента к следующему.
Пример: МассивПокупателей=[21,10,45,48,37,12,12,34,17,10] КоличествоКасс=6. В данном случае ответ будет 48.

(0) и ? в чем сложность то ? Упорядочить подмножества и прибавить следующие + посчитать максимум ?

Такое в школе, на уроках информатики проходят, классе в 8-ом

(0) Более оптимально чем что?

(0) О какой оптимальности вообще речь идёт при "покупатели подходят к кассам в порядке очереди"?

(4) у меня получилось вот так, может можно еще как то оптимальней
МассивКасс=Новый Массив;
    Для к=1 По КоличествоКасс Цикл
        МассивКасс.Добавить(0);    
    КонецЦикла;
    Для Каждого ТекВремя Из МассивПокупателей Цикл
        ИндексКассыМин=МассивКасс.Найти(Минимум(МассивКасс));
        МассивКасс[ИндексКассыМин]=МассивКасс[ИндексКассыМин]+ТекВремя;
    КонецЦикла;
    Возврат Максимум(МассивКасс);

(4) оптимальней в плане написания кода

(6) Расшифруй.
По времени выполнения, по расходу памяти, по нравится/не нравится

(7) по времени выполнения и читаемости

(8) это два разных алгоритма

(9) тогда по времени выполнения

(10)  
Функция определитьМаксимальноеВремяВЭтойЗадаче()
Возврат 48;
КонецФункции

(5) (10) тогда
МассивКасс.Найти(Минимум(МассивКасс));
выглядит сомнительно. Один раз отсортировать и потом поддерживать упорядоченность возможно оптимальнее

(12) а как ты один раз отсортируешь, если у тебя в массив касс в цикле вставляются покупатели в ячейку с меньшим числом? Массив покупателей тоже упорядочить нельзя, так как они в даются с фиксированным порядком

Задача вообще в другом состоит. По описанию, которое дано в (0) - надо просто посчитать количество минут, требующихся на обслуживание. "в супермаркете стоит очередь к кассам самообслуживания. Ваша задача - написать функцию для расчета общего времени, необходимого для обслуживания всех клиентов". То есть они уже стоят по кассам и известно время обслуживания каждого клиента. Явно задачка изначальная предполагалась более сложной быть.
Вангую, что задача в том, что есть массив клиентов, для которых известно время, которое будет затрачено на обслуживание. И задача в том, чтобы распределить людей по 6 кассам так, чтобы общее время их обслуживания было минимальным (то есть простой касс, обслуживших свою часть клиентов был минимальный).
Так что оптимальность заключается в этом, а не в читаемости кода или скорости его выполнения.

(13) хочешь заморочится - минимумы/максимумы/индекс кассы с минимальным временем в цикле динамически определяй, а не функция ми вычисляй

(13) Отсортировали. Добавили в первую ячейку, сдвинули её (поменяли местами) если надо.

(14) просто представь, тебе говорят, пропусти вот этих 3 покупаталей, чтобы общее время было меньше и пофиг, что ты пришел раньше к кассе))

в (5) вполне нормальное решение навскидку

(17) короче кури ТМО

(17) чиво? это абстрактная задачка. Просто представь, тебе говорят "на вас потребуется 48 минут, а на вашего соседа 12", а вы оба с яблоком

(20) абстрактная да, но в ней явно указано, что покупатели идут по порядку. Не всегда есть возможность упорядочить множество, чтобы получить минимальное время, иногда приходится мириться с фиксированной очередью.

(19) ТМО - Техника модификации опыта?)

(21) по порядку в очереди, но не по порядку в кассу. все нормально в задаче как (14) пишет

(22) теория массового обслуживания

(23) Если по порядку в очереди, то никакой оптимизации сверх "идти в свободную кассу" не придумаешь. Или всё-таки есть смысл держать свободную кассу для покупателя с большой тележкой, что-то засомневался.

(25) А никакой другой оптимизации на практике и не получится. Вся очередь заранее неизвестна и пополняется в процессе обслуживания. Никакой оптимизации в духе "Мы знаем, что через полчаса в очереди будет большая тележка, оставим сейчас  под нее кассу" сделать не удастся.

(0) Это неинтересный пример
Вот куда интереснее
МассивПокупателей=[1,1,10] КоличествоКасс=2
Ответ может быть 11, если решать в лоб, а может быть 10
И 10 правильнее, но только в случае, если покупателей расставляют принудительно, потому что иначе первый займет первую кассу, второй вторую, и уже получится никак не 10

(5) Твой вариант для (27) даст 11 вместо 10

+(28) Хотя, если считать реальное минимальное время, то есть без управления покупателями, то 11 правильнее

(27) в (0) не стоит задача оптимизировать же. Нужно посчитать время. Алгоритм (5) с этим справляется.

(25) как раз смысл рассмотреть все варианты и выбрать наилучший.
самое тупое решение методом "прямого перебора" каждому покупателю даем индекс кассы куда он пошел от 0 до колво касс-1, считаем все суммы минут находим минимум.
каждый вариант описывается числом от 00000 до FFFFF(в системе счисления с основанием кол-во касс) сложность такого решения (кассы ) в степени (покупатели). очевидно просят найти решение c  линейной или логарифмической сложностью

(5) Давай полный код, вместе со своими минимумами и максимуми. Скажем с точкой входа ВремяОбслуживания(МассивПокупателей, КоличествоКасс)

(30) Я по началу вообще вычитал это минимальное время на заполненных кассах, чтобы получить свободную кассу(0). А потом к этому элементу массива добавлял следующий элемент из покупателей. Это минимальное время я складывал в результат. Когда доходил до последнего покупателя, добавлял его в массив касс и брал максимальное значение из массива и добавлял его к результату. Но потом допер, что вычитать ничего не надо и пришел к коду 5.

(32)
&НаКлиенте
Функция Минимум(Массив)
    Минимум=Массив[0];
    Для Каждого ТекЧисло Из Массив Цикл
        Если Минимум>ТекЧисло Тогда
            Минимум=ТекЧисло;    
        КонецЕсли;    
    КонецЦикла;
    Возврат Минимум;
КонецФункции

&НаКлиенте
Функция Максимум(Массив)
    Максимум=Массив[0];
    Для Каждого ТекЧисло Из Массив Цикл
        Если Максимум<ТекЧисло Тогда
            Максимум=ТекЧисло;    
        КонецЕсли;    
    КонецЦикла;
    Возврат Максимум;
КонецФункции

(34) Странно, что 1ска не умеет сама определять мин/макс из массива чисел...

(35) типо min(Массив)

(34) максимум можно прямо в цикле динамически определять:

МаксимальноеВремя = 0;
Для Каждого ТекВремя Из МассивПокупателей Цикл
    ИндексКассыМин=МассивКасс.Найти(Минимум(МассивКасс));
    МассивКасс[ИндексКассыМин]=МассивКасс[ИндексКассыМин]+ТекВремя;
    Если МаксимальноеВремя<МассивКасс[ИндексКассыМин] Тогда
        МаксимальноеВремя=МассивКасс[ИндексКассыМин];
    КонецЕсли;
КонецЦикла;
Возврат МаксимальноеВремя;

(31) Начать надо с теории. Возможна ли в принципе ситуация, что
1. покупатели обслуживаются по очереди
2. держать свободную кассу выгодно (с точки зрения критериев (14))
Имхо такая ситуация невозможно, а значит отправить на свободную кассу и есть оптимальная стратегия - задача простая.

А вот если разрешить покупателям пропускать, то задача гораздо интереснее

(35) Нет в 1С "массива чисел". Есть просто массив, поэтому вполне логично отсутствие таких функий

(39) В запрос же можно запихнуть массив и получить максимум/минимум, и пофиг, число это, или строка. Можно было бы и в синтаксис воткнуть такую возможность...

(36)  
СписокЗначений = Новый СписокЗначений;
СписокЗначений.ЗагрузитьЗначения(МассивЧисел);
СписокЗначений.СортироватьПоЗначению();
МассивЧисел = СписокЗначений.ВыгрузитьЗначения();

(41) как вариант)

(40) Никакие операции с массивами в запросе не поддерживаются кроме проверки условия "В"

Если не особо включать голову по алгоритму, то можно раза в два быстрее.

Функция ВремяОбслуживания(МассивПокупателей, КоличествоКасс)
    
    НаборКасс = Новый ТаблицаЗначений;
    НаборКасс.Колонки.Добавить("Время", Новый ОписаниеТипов("Число"));
    
    ИндексПоследнегоПокупателя = МассивПокупателей.ВГраница();
    ИндексПокупателя = 0;
    
    Пока Истина Цикл
        НаборКасс.Добавить().Время = МассивПокупателей[ИндексПокупателя];
        ИндексПокупателя = ИндексПокупателя + 1;
        
        Если ИндексПокупателя > КоличествоКасс Или ИндексПокупателя > ИндексПоследнегоПокупателя Тогда
            Прервать;
        КонецЕсли;
        
    КонецЦикла;
    
    Для Индекс = ИндексПокупателя По ИндексПоследнегоПокупателя Цикл
        НаборКасс.Сортировать("Время");
        НаборКасс[0].Время = НаборКасс[0].Время + МассивПокупателей[Индекс];
    КонецЦикла;
    
    НаборКасс.Сортировать("Время УБЫВ");
    Возврат НаборКасс[0].Время;
    
КонецФункции

(44) вот уже что-то интересное, вечерком сравню по времени выполнения

(44) сортировать на каждом шаге - сомнительно по скорости. Но если встроенный алгоритм сортировки оптимально работает на почти упорядоченных данных, то может и ничего

(0) Эээ нет

>задача - написать функцию для расчета общего времени, необходимого для обслуживания всех клиентов!
и
>В данном случае ответ будет 48

Не стыкуются!
Можно по разному распределять покупателей по шести кассам и получать разный ответ общего времени от минимального до максимального.

Лично я бы упорядочил юзеров по категориям "тормознутости" и сувал в разные очереди. Типа шустрые в очередь шустрых, тормозов в очередь к тормозам, а середнячков к таким же

(47) тогда на 2х кассах массив [1,10,10,1,1,1,1,1,1,1,1,1] даст 20 минут(тормоза 10+10 в одну кассу), а должен дать 15 - по одному тормозу на кассу

ИМХО, разновидность "задачи о рюкзаке".

(49) в (14) что-то похожее. В (0) же простенькая задачка

(48) Есть такая штука как "средняя удовлетворенность покупателя".
Лучше 1 недовольный чем 10

(50) Да? Тогда сумма всех элементов массива тоже будет удовлетворять условию задачи и будет считаться быстрее всего.

Вот просто все покупатели пошли на одну кассу. Там продавщица самая сисястая.

(47) >> Можно по разному распределять покупателей по шести кассам

Нельзя по условию задачи

Так как оптимально решить задачу очень легко, решил сделать наоборот не оптимальное решение задачи, на JS, с использованием таймера, офигевайте:

const begin = performance.now()
const buyers = [ 21, 10, 45, 48, 37, 12, 12, 34, 17, 10 ]
const registers = new Array(6).fill(true)
const freeRegister = () => {
    registers.pop()
    !registers.length && console.log(Math.floor((performance.now() - begin) / 100))
}
const service = buyer => buyer ? setTimeout(nextBuyer, 100 * buyer) : freeRegister()
const nextBuyer = () => service(buyers.shift())
registers.forEach(nextBuyer)

Классическая электронная очередь.
Первый попадает на оператора и удаляется с начала массива (ну или сдвигаем курсор)далее следующий.
Получаем время окончания обслуживания для каждой точки обслуживания,и в момент окончания берём следующий элемент из очереди,добавляем в таблицу очередности и опять не сортируем.
Соответственно,когда что-то из таблицы очередности удаляем,то счётчик потраченного времени увеличиваем на эту величину,а из остальных значений ее вычитаем.
Вот и все.
Таблицу поддерживаем в отсортированном состоянии,вставка в упорядоченный массив-делегтнм пополам,так как из какого-то места удалили,то сдвигать нужно только кусок массива.

(49) Удивлен, что только к 49му сообщению о нем вспомнили.
Какие есть решения кроме полного перебора?

(57) Решения чего? В (0) примитивная задача, или ты (14) собрался решать

(58) Да, я про (14) и (27)

(59) О! Я (27) пропустил, а там как раз контрпример для (38). Интересненько.

В одном из магазинов видел экспресс-кассы. Работник магазина если видит что в очереди стоит человек с маленьким количеством покупок, и при этом одна из экспресс-касс освобождается или там маленькая очередь, то выдергивает человека из основной очереди, и направляет в очередь экспресс-касс.

сейчас время электронных очередей. из полученного талончика примерно известно время оказания услуги по типу, который выбрал посетитель. можно оптимизировать.
оптимизировать очередь необходимо на каждом проходе, поскольку покупатели нередко уходят из очереди, кассы добавляются или закрываются на перерыв.
пропускать вперед покупателей с одной жвачкой или одной бутылкой воды - нормально.
короче задачу надо существенно дополнять для более менее приближения к реальности.
а использовать критерием "минимальное время выполнения" - звучит бредово. вам без разницы в действительности займет расчет 0,1 или 0,01 секунду.
вам нужна максимальная пропускная способность в указанных ограничениях.

(57) Вики: "задача о рюкзаке относится к классу NP-полных, и для неё нет полиномиального алгоритма, решающего её за разумное время. Поэтому при решении задачи о рюкзаке необходимо выбирать между точными алгоритмами, которые неприменимы для «больших» рюкзаков, и приближенными, которые работают быстро, но не гарантируют оптимального решения задачи"

(57) Тут выше упоминали динамическое программирование. Я не в курсе, что это такое :) Но пишут, что методами динамического программирования при ряде ограничений на входные данные дает оптимальное решение с хорошей производительностью.

(44) Попробовал ваш код на примере следующих начальных данных:
        Строка="21,10,45,48,37,12,12,34,17,10,";
    Для к=1 По 10 Цикл
        Строка=Строка+Строка;    
    КонецЦикла;
    МассивПодстрок=СтроковыеФункцииКлиентСервер.РазложитьСтрокуВМассивПодстрок(Строка,",",Истина,Истина);
    Массив=Новый Массив;
    Для Каждого ТекСтрока Из МассивПодстрок Цикл
        Массив.Добавить(Число(ТекСтрока));    
    КонецЦикла;
    Сообщить(ВремяОбслуживания(Массив, 6));
Ваш код ответ дал 36000, мой 41994
время выполнения 0.2806 ваш код, 0.000934 мой код

(62) электронная очередь позволяет пропускать только клиентов с другим классом обслуживания,и да она в этом случае удобна для vip-клиентов,так как им даётся номер другой серии и его сразу пускают на освободившуюся стойку,и никто не жужжит
А вот если номер одной и той же серии пустить раньше другого,то будет скандал.

(65) Хрень какая-то. Мой кода дал ответ 48 на этом массиве начальных данных, что является правильным ответом.

Итак массив структур в каждой номер кассы и время выполнения операции.
При добавлении в общем кассу обслуживаемого во время выполнения ставим время обслуживания и сортируем массив,чтобы в нем было упорядочивание по возрастанию.
Если первый элемент выполнения имеет ненулевое время,то вычитаем из всех времён выполненения это значение и добавляем его в счётчик выполнения.
Если там ноль,то можно добавлять следующее значение из массива.
Если добавлять нечего,то идём по массиву до конца,вычитая время каждого элемента из остальных и добавляя значение в счётчик времени.
Когда мы пройдем весь массив,то получив в счётчике времени ответ.

(67) Обратите внимание, там Строка - 10 раз удваивается.

(69) Действительно. Тогда все верно, (4) довольно оптимальное решение, лучше трудно придумать.

Вот вариант более быстрого и простого, но немного неточного. На той же строке дает результат 41984, погрешность 0.02%, но ОЧЕНЬ быстро.

function line(buyers) {
    return buyers.reduce((c, b) => c + b) / 6;
}

Если строку удвоить 22 раза, то разница в скорости еще более огромная, а погрешность около 5.8е-6

Up!

В этой простой задачке самое сложное - это на каждом шаге находить минимальное время начала обслуживания среди всех касс. То есть нам нужна структура данных, поддерживающая операции: добавление элемента, удаление минимального элемента. Для этого обычно используют двоичную кучу (binary heap), сложность обеих операций в ней: O(log(n)). В результате решение будет следующим:

Пусть у нас n покупателей, m касс, а время обслуживания i-ого покупателя: time[i].

1. Инициализируем кучу, добавив в нее m нулей.

2. Для i-ого покупателя достаем минимальный элемент minTime из кучи (это будет время начала обслуживания) и добавляем в кучу minTime + time[i] (время окончания обслуживания).

3. Достаем все элементы из кучи, пока она не станет пустой. Последний элемент, который мы достали - это ответ задачи.

Сложность выполнения основного шага алгоритма будет O(n*log(m)).