Вход | Регистрация
 

Оптимальное решение задачки

Оптимальное решение задачки
Я
   Kassern
 
17.12.20 - 16:39
Добрый день. Наткнулся в инете на интересную задачку. Интересно, сможет кто-нить ее решить более оптимально. Суть задачи: в супермаркете стоит очередь к кассам самообслуживания. Ваша задача - написать функцию для расчета общего времени, необходимого для обслуживания всех клиентов!
МассивПокупателей: массив положительных целых чисел, представляющих очередь. Каждое целое число представляет клиента,и его значение - это количество времени, которое ему требуется для обслуживания.
Покупатели подходят к кассам в порядке очереди от первого элемента к следующему.
Пример: МассивПокупателей=[21,10,45,48,37,12,12,34,17,10] КоличествоКасс=6. В данном случае ответ будет 48.
   Ёпрст
 
1 - 17.12.20 - 16:44
(0) и ? в чем сложность то ? Упорядочить подмножества и прибавить следующие + посчитать максимум ?
   Ёпрст
 
2 - 17.12.20 - 16:45
Такое в школе, на уроках информатики проходят, классе в 8-ом
   acht
 
3 - 17.12.20 - 16:47
(0) Более оптимально чем что?
   RomanYS
 
4 - 17.12.20 - 16:47
(0) О какой оптимальности вообще речь идёт при "покупатели подходят к кассам в порядке очереди"?
   Kassern
 
5 - 17.12.20 - 16:48
(4) у меня получилось вот так, может можно еще как то оптимальней
МассивКасс=Новый Массив;
    Для к=1 По КоличествоКасс Цикл
        МассивКасс.Добавить(0);    
    КонецЦикла;
    Для Каждого ТекВремя Из МассивПокупателей Цикл
        ИндексКассыМин=МассивКасс.Найти(Минимум(МассивКасс));
        МассивКасс[ИндексКассыМин]=МассивКасс[ИндексКассыМин]+ТекВремя;
    КонецЦикла;
    Возврат Максимум(МассивКасс);
   Kassern
 
6 - 17.12.20 - 16:48
(4) оптимальней в плане написания кода
   acht
 
7 - 17.12.20 - 16:49
(6) Расшифруй.
По времени выполнения, по расходу памяти, по нравится/не нравится
   Kassern
 
8 - 17.12.20 - 16:50
(7) по времени выполнения и читаемости
   Малыш Джон
 
9 - 17.12.20 - 16:50
(8) это два разных алгоритма
   Kassern
 
10 - 17.12.20 - 16:51
(9) тогда по времени выполнения
   Малыш Джон
 
11 - 17.12.20 - 16:53
(10)  
Функция определитьМаксимальноеВремяВЭтойЗадаче()
Возврат 48;
КонецФункции
   RomanYS
 
12 - 17.12.20 - 16:53
(5) (10) тогда
МассивКасс.Найти(Минимум(МассивКасс));
выглядит сомнительно. Один раз отсортировать и потом поддерживать упорядоченность возможно оптимальнее
   Kassern
 
13 - 17.12.20 - 16:56
(12) а как ты один раз отсортируешь, если у тебя в массив касс в цикле вставляются покупатели в ячейку с меньшим числом? Массив покупателей тоже упорядочить нельзя, так как они в даются с фиксированным порядком
   MouHacTaBHuk
 
14 - 17.12.20 - 16:57
Задача вообще в другом состоит. По описанию, которое дано в (0) - надо просто посчитать количество минут, требующихся на обслуживание. "в супермаркете стоит очередь к кассам самообслуживания. Ваша задача - написать функцию для расчета общего времени, необходимого для обслуживания всех клиентов". То есть они уже стоят по кассам и известно время обслуживания каждого клиента. Явно задачка изначальная предполагалась более сложной быть.
Вангую, что задача в том, что есть массив клиентов, для которых известно время, которое будет затрачено на обслуживание. И задача в том, чтобы распределить людей по 6 кассам так, чтобы общее время их обслуживания было минимальным (то есть простой касс, обслуживших свою часть клиентов был минимальный).
Так что оптимальность заключается в этом, а не в читаемости кода или скорости его выполнения.
   Малыш Джон
 
15 - 17.12.20 - 16:58
(13) хочешь заморочится - минимумы/максимумы/индекс кассы с минимальным временем в цикле динамически определяй, а не функция ми вычисляй
   RomanYS
 
16 - 17.12.20 - 16:58
(13) Отсортировали. Добавили в первую ячейку, сдвинули её (поменяли местами) если надо.
   Kassern
 
17 - 17.12.20 - 16:58
(14) просто представь, тебе говорят, пропусти вот этих 3 покупаталей, чтобы общее время было меньше и пофиг, что ты пришел раньше к кассе))
   Малыш Джон
 
18 - 17.12.20 - 16:58
в (5) вполне нормальное решение навскидку
   Малыш Джон
 
19 - 17.12.20 - 16:59
(17) короче кури ТМО
   MouHacTaBHuk
 
20 - 17.12.20 - 17:00
(17) чиво? это абстрактная задачка. Просто представь, тебе говорят "на вас потребуется 48 минут, а на вашего соседа 12", а вы оба с яблоком
   Kassern
 
21 - 17.12.20 - 17:02
(20) абстрактная да, но в ней явно указано, что покупатели идут по порядку. Не всегда есть возможность упорядочить множество, чтобы получить минимальное время, иногда приходится мириться с фиксированной очередью.
   Kassern
 
22 - 17.12.20 - 17:04
(19) ТМО - Техника модификации опыта?)
   Timon1405
 
23 - 17.12.20 - 17:05
(21) по порядку в очереди, но не по порядку в кассу. все нормально в задаче как (14) пишет
   Малыш Джон
 
24 - 17.12.20 - 17:07
(22) теория массового обслуживания
   RomanYS
 
25 - 17.12.20 - 17:12
(23) Если по порядку в очереди, то никакой оптимизации сверх "идти в свободную кассу" не придумаешь. Или всё-таки есть смысл держать свободную кассу для покупателя с большой тележкой, что-то засомневался.
   Малыш Джон
 
26 - 17.12.20 - 17:15
(25) А никакой другой оптимизации на практике и не получится. Вся очередь заранее неизвестна и пополняется в процессе обслуживания. Никакой оптимизации в духе "Мы знаем, что через полчаса в очереди будет большая тележка, оставим сейчас  под нее кассу" сделать не удастся.
   PR
 
27 - 17.12.20 - 17:15
(0) Это неинтересный пример
Вот куда интереснее
МассивПокупателей=[1,1,10] КоличествоКасс=2
Ответ может быть 11, если решать в лоб, а может быть 10
И 10 правильнее, но только в случае, если покупателей расставляют принудительно, потому что иначе первый займет первую кассу, второй вторую, и уже получится никак не 10
   PR
 
28 - 17.12.20 - 17:16
(5) Твой вариант для (27) даст 11 вместо 10
   PR
 
29 - 17.12.20 - 17:17
+(28) Хотя, если считать реальное минимальное время, то есть без управления покупателями, то 11 правильнее
   Малыш Джон
 
30 - 17.12.20 - 17:19
(27) в (0) не стоит задача оптимизировать же. Нужно посчитать время. Алгоритм (5) с этим справляется.
 
 
   Timon1405
 
31 - 17.12.20 - 17:24
(25) как раз смысл рассмотреть все варианты и выбрать наилучший.
самое тупое решение методом "прямого перебора" каждому покупателю даем индекс кассы куда он пошел от 0 до колво касс-1, считаем все суммы минут находим минимум.
каждый вариант описывается числом от 00000 до FFFFF(в системе счисления с основанием кол-во касс) сложность такого решения (кассы ) в степени (покупатели). очевидно просят найти решение c  линейной или логарифмической сложностью
   acht
 
32 - 17.12.20 - 17:24
(5) Давай полный код, вместе со своими минимумами и максимуми. Скажем с точкой входа ВремяОбслуживания(МассивПокупателей, КоличествоКасс)
   Kassern
 
33 - 17.12.20 - 17:27
(30) Я по началу вообще вычитал это минимальное время на заполненных кассах, чтобы получить свободную кассу(0). А потом к этому элементу массива добавлял следующий элемент из покупателей. Это минимальное время я складывал в результат. Когда доходил до последнего покупателя, добавлял его в массив касс и брал максимальное значение из массива и добавлял его к результату. Но потом допер, что вычитать ничего не надо и пришел к коду 5.
   Kassern
 
34 - 17.12.20 - 17:27
(32)
&НаКлиенте
Функция Минимум(Массив)
    Минимум=Массив[0];
    Для Каждого ТекЧисло Из Массив Цикл
        Если Минимум>ТекЧисло Тогда
            Минимум=ТекЧисло;    
        КонецЕсли;    
    КонецЦикла;
    Возврат Минимум;
КонецФункции

&НаКлиенте
Функция Максимум(Массив)
    Максимум=Массив[0];
    Для Каждого ТекЧисло Из Массив Цикл
        Если Максимум<ТекЧисло Тогда
            Максимум=ТекЧисло;    
        КонецЕсли;    
    КонецЦикла;
    Возврат Максимум;
КонецФункции
   Kassern
 
35 - 17.12.20 - 17:29
(34) Странно, что 1ска не умеет сама определять мин/макс из массива чисел...
   Kassern
 
36 - 17.12.20 - 17:29
(35) типо min(Массив)
   Малыш Джон
 
37 - 17.12.20 - 17:31
(34) максимум можно прямо в цикле динамически определять:

МаксимальноеВремя = 0;
Для Каждого ТекВремя Из МассивПокупателей Цикл
    ИндексКассыМин=МассивКасс.Найти(Минимум(МассивКасс));
    МассивКасс[ИндексКассыМин]=МассивКасс[ИндексКассыМин]+ТекВремя;
    Если МаксимальноеВремя<МассивКасс[ИндексКассыМин] Тогда
        МаксимальноеВремя=МассивКасс[ИндексКассыМин];
    КонецЕсли;
КонецЦикла;
Возврат МаксимальноеВремя;
   RomanYS
 
38 - 17.12.20 - 17:33
(31) Начать надо с теории. Возможна ли в принципе ситуация, что
1. покупатели обслуживаются по очереди
2. держать свободную кассу выгодно (с точки зрения критериев (14))
Имхо такая ситуация невозможно, а значит отправить на свободную кассу и есть оптимальная стратегия - задача простая.

А вот если разрешить покупателям пропускать, то задача гораздо интереснее
   RomanYS
 
39 - 17.12.20 - 17:34
(35) Нет в 1С "массива чисел". Есть просто массив, поэтому вполне логично отсутствие таких функий
   Kassern
 
40 - 17.12.20 - 17:36
(39) В запрос же можно запихнуть массив и получить максимум/минимум, и пофиг, число это, или строка. Можно было бы и в синтаксис воткнуть такую возможность...
   Малыш Джон
 
41 - 17.12.20 - 17:38
(36)  
СписокЗначений = Новый СписокЗначений;
СписокЗначений.ЗагрузитьЗначения(МассивЧисел);
СписокЗначений.СортироватьПоЗначению();
МассивЧисел = СписокЗначений.ВыгрузитьЗначения();
   Kassern
 
42 - 17.12.20 - 17:40
(41) как вариант)
   RomanYS
 
43 - 17.12.20 - 17:43
(40) Никакие операции с массивами в запросе не поддерживаются кроме проверки условия "В"
   acht
 
44 - 17.12.20 - 17:48
Если не особо включать голову по алгоритму, то можно раза в два быстрее.

Функция ВремяОбслуживания(МассивПокупателей, КоличествоКасс)
    
    НаборКасс = Новый ТаблицаЗначений;
    НаборКасс.Колонки.Добавить("Время", Новый ОписаниеТипов("Число"));
    
    ИндексПоследнегоПокупателя = МассивПокупателей.ВГраница();
    ИндексПокупателя = 0;
    
    Пока Истина Цикл
        НаборКасс.Добавить().Время = МассивПокупателей[ИндексПокупателя];
        ИндексПокупателя = ИндексПокупателя + 1;
        
        Если ИндексПокупателя > КоличествоКасс Или ИндексПокупателя > ИндексПоследнегоПокупателя Тогда
            Прервать;
        КонецЕсли;
        
    КонецЦикла;
    
    Для Индекс = ИндексПокупателя По ИндексПоследнегоПокупателя Цикл
        НаборКасс.Сортировать("Время");
        НаборКасс[0].Время = НаборКасс[0].Время + МассивПокупателей[Индекс];
    КонецЦикла;
    
    НаборКасс.Сортировать("Время УБЫВ");
    Возврат НаборКасс[0].Время;
    
КонецФункции
   Kassern
 
45 - 17.12.20 - 17:51
(44) вот уже что-то интересное, вечерком сравню по времени выполнения
   RomanYS
 
46 - 17.12.20 - 17:58
(44) сортировать на каждом шаге - сомнительно по скорости. Но если встроенный алгоритм сортировки оптимально работает на почти упорядоченных данных, то может и ничего
   Garykom
 
47 - 17.12.20 - 18:18
(0) Эээ нет

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

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

Лично я бы упорядочил юзеров по категориям "тормознутости" и сувал в разные очереди. Типа шустрые в очередь шустрых, тормозов в очередь к тормозам, а середнячков к таким же
   Timon1405
 
48 - 17.12.20 - 18:22
(47) тогда на 2х кассах массив [1,10,10,1,1,1,1,1,1,1,1,1] даст 20 минут(тормоза 10+10 в одну кассу), а должен дать 15 - по одному тормозу на кассу
   fisher
 
49 - 17.12.20 - 18:39
ИМХО, разновидность "задачи о рюкзаке".
   RomanYS
 
50 - 17.12.20 - 18:48
(49) в (14) что-то похожее. В (0) же простенькая задачка
   Garykom
 
51 - 17.12.20 - 18:50
(48) Есть такая штука как "средняя удовлетворенность покупателя".
Лучше 1 недовольный чем 10
   fisher
 
52 - 17.12.20 - 18:51
(50) Да? Тогда сумма всех элементов массива тоже будет удовлетворять условию задачи и будет считаться быстрее всего.
   fisher
 
53 - 17.12.20 - 18:52
Вот просто все покупатели пошли на одну кассу. Там продавщица самая сисястая.
   Доктор Манхэттен
 
54 - 17.12.20 - 19:08
(47) >> Можно по разному распределять покупателей по шести кассам

Нельзя по условию задачи
   Доктор Манхэттен
 
55 - 17.12.20 - 19:51
Так как оптимально решить задачу очень легко, решил сделать наоборот не оптимальное решение задачи, на 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)
   ДедМорроз
 
56 - 17.12.20 - 20:31
Классическая электронная очередь.
Первый попадает на оператора и удаляется с начала массива (ну или сдвигаем курсор)далее следующий.
Получаем время окончания обслуживания для каждой точки обслуживания,и в момент окончания берём следующий элемент из очереди,добавляем в таблицу очередности и опять не сортируем.
Соответственно,когда что-то из таблицы очередности удаляем,то счётчик потраченного времени увеличиваем на эту величину,а из остальных значений ее вычитаем.
Вот и все.
Таблицу поддерживаем в отсортированном состоянии,вставка в упорядоченный массив-делегтнм пополам,так как из какого-то места удалили,то сдвигать нужно только кусок массива.
   DTX 4th
 
57 - 17.12.20 - 20:46
(49) Удивлен, что только к 49му сообщению о нем вспомнили.
Какие есть решения кроме полного перебора?
   RomanYS
 
58 - 17.12.20 - 20:50
(57) Решения чего? В (0) примитивная задача, или ты (14) собрался решать
   DTX 4th
 
59 - 17.12.20 - 20:56
(58) Да, я про (14) и (27)
   RomanYS
 
60 - 17.12.20 - 21:05
(59) О! Я (27) пропустил, а там как раз контрпример для (38). Интересненько.
 
 
   Доктор Манхэттен
 
61 - 17.12.20 - 21:13
В одном из магазинов видел экспресс-кассы. Работник магазина если видит что в очереди стоит человек с маленьким количеством покупок, и при этом одна из экспресс-касс освобождается или там маленькая очередь, то выдергивает человека из основной очереди, и направляет в очередь экспресс-касс.
   Bigbro
 
62 - 18.12.20 - 04:42
сейчас время электронных очередей. из полученного талончика примерно известно время оказания услуги по типу, который выбрал посетитель. можно оптимизировать.
оптимизировать очередь необходимо на каждом проходе, поскольку покупатели нередко уходят из очереди, кассы добавляются или закрываются на перерыв.
пропускать вперед покупателей с одной жвачкой или одной бутылкой воды - нормально.
короче задачу надо существенно дополнять для более менее приближения к реальности.
а использовать критерием "минимальное время выполнения" - звучит бредово. вам без разницы в действительности займет расчет 0,1 или 0,01 секунду.
вам нужна максимальная пропускная способность в указанных ограничениях.
   fisher
 
63 - 18.12.20 - 10:16
(57) Вики: "задача о рюкзаке относится к классу NP-полных, и для неё нет полиномиального алгоритма, решающего её за разумное время. Поэтому при решении задачи о рюкзаке необходимо выбирать между точными алгоритмами, которые неприменимы для «больших» рюкзаков, и приближенными, которые работают быстро, но не гарантируют оптимального решения задачи"
   fisher
 
64 - 18.12.20 - 10:20
(57) Тут выше упоминали динамическое программирование. Я не в курсе, что это такое :) Но пишут, что методами динамического программирования при ряде ограничений на входные данные дает оптимальное решение с хорошей производительностью.
   Kassern
 
65 - 26.12.20 - 13:25
(44) Попробовал ваш код на примере следующих начальных данных:
        Строка="21,10,45,48,37,12,12,34,17,10,";
    Для к=1 По 10 Цикл
        Строка=Строка+Строка;    
    КонецЦикла;
    МассивПодстрок=СтроковыеФункцииКлиентСервер.РазложитьСтрокуВМассивПодстрок(Строка,",",Истина,Истина);
    Массив=Новый Массив;
    Для Каждого ТекСтрока Из МассивПодстрок Цикл
        Массив.Добавить(Число(ТекСтрока));    
    КонецЦикла;
    Сообщить(ВремяОбслуживания(Массив, 6));
Ваш код ответ дал 36000, мой 41994
время выполнения 0.2806 ваш код, 0.000934 мой код
   ДедМорроз
 
66 - 26.12.20 - 15:59
(62) электронная очередь позволяет пропускать только клиентов с другим классом обслуживания,и да она в этом случае удобна для vip-клиентов,так как им даётся номер другой серии и его сразу пускают на освободившуюся стойку,и никто не жужжит
А вот если номер одной и той же серии пустить раньше другого,то будет скандал.
   Доктор Манхэттен
 
67 - 27.12.20 - 01:57
(65) Хрень какая-то. Мой кода дал ответ 48 на этом массиве начальных данных, что является правильным ответом.
   ДедМорроз
 
68 - 27.12.20 - 12:08
Итак массив структур в каждой номер кассы и время выполнения операции.
При добавлении в общем кассу обслуживаемого во время выполнения ставим время обслуживания и сортируем массив,чтобы в нем было упорядочивание по возрастанию.
Если первый элемент выполнения имеет ненулевое время,то вычитаем из всех времён выполненения это значение и добавляем его в счётчик выполнения.
Если там ноль,то можно добавлять следующее значение из массива.
Если добавлять нечего,то идём по массиву до конца,вычитая время каждого элемента из остальных и добавляя значение в счётчик времени.
Когда мы пройдем весь массив,то получив в счётчике времени ответ.
   Salimbek
 
69 - 27.12.20 - 13:49
(67) Обратите внимание, там Строка - 10 раз удваивается.
   Доктор Манхэттен
 
70 - 28.12.20 - 09:04
(69) Действительно. Тогда все верно, (4) довольно оптимальное решение, лучше трудно придумать.

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

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

Если строку удвоить 22 раза, то разница в скорости еще более огромная, а погрешность около 5.8е-6
   Доктор Манхэттен
 
71 - 30.12.20 - 04:10
Up!
   _DAle_
 
72 - 30.12.20 - 10:40
В этой простой задачке самое сложное - это на каждом шаге находить минимальное время начала обслуживания среди всех касс. То есть нам нужна структура данных, поддерживающая операции: добавление элемента, удаление минимального элемента. Для этого обычно используют двоичную кучу (binary heap), сложность обеих операций в ней: O(log(n)). В результате решение будет следующим:

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

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

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

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

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


Список тем форума
 
ВНИМАНИЕ! Если вы потеряли окно ввода сообщения, нажмите Ctrl-F5 или Ctrl-R или кнопку "Обновить" в браузере.
Тема не обновлялась длительное время, и была помечена как архивная. Добавление сообщений невозможно.
Но вы можете создать новую ветку и вам обязательно ответят!
Каждый час на Волшебном форуме бывает более 2000 человек.