Здравствуйте, Ватакуси, Вы писали:
В>Мне сказали, что "обычно" выполняют за 40 минут.
"И вы говорите".
В то, что алгоритм какой-нибудь сильный олимпиадник за 40 минут напишет, я могу поверить. Но, там кроме алгоритма еще вагон всякой мишуры будет.
Так что, реально тут работы на несколько дней, скорее всего.
В>Ну, и риторический вопрос — стали бы вы это делать?
Здравствуйте, Lazytech, Вы писали:
L>Он вроде не проходил сквозь стены. Человек просто наловчился делать ступеньки выстрелами из клеевой пушки и взбираться по этим ступенькам на расположенный выше этаж.
Как минимум один раз на 00:06, дальше я внимательно не смотрел.
$>Да ладно. Там нужно прикрутить прикрутить оптимизационный solver (какой-нить minimax). За 24 часа можно уложиться- это часа 2-3 на почитать википедию, реализовать алгоритм и отладить еще 2-3 часа.
What? Решать дискретную задачу о рюкзаке минимаксом или оптимизационным solver'ом? Удачи
Если не понятно, откуда там рюкзак: Даем на вход все станции wind. Они fixed cost, fixed energy (после умножения на 10 — вся энергия в выводе — целые числа). Нужно их напаковать на суммарную энергию за минимум денег.
8 часов минимум, но скорей всего 16. Нет смысла писать половинчатое решение, ну а если делать продуктовое качество, то меньше 8 точно не будет. А при их постановке требований сами собой напрашиваются не только модульные, но и интеграционные тесты, так что там работы реально много.
В>Ну, и риторический вопрос — стали бы вы это делать?
Если бы их устроил мой расчет времени + у них действительно хорошая ЗП, то да, делал бы.
Здравствуйте, Ватакуси, Вы писали:
В>Мне сказали, что "обычно" выполняют за 40 минут.
За 40 минут там будет обычный олимпиадный говнокод, совершенно непонятно что с его помощью можно показать работодателю. Что умеешь наговнокодить, если очень припрёт? Сомнительный плюс.
В>Ну, и риторический вопрос — стали бы вы это делать?
Нет. Я уже не в том возрасте, чтобы делать тестовые задания.
Здравствуйте, gandjustas, Вы писали:
G>Симплекс метод за 40 минут? 99% программистов его не напишут вообще. G>Я может невнимательно читал, но на вид это «непрерывная задача о рюкзаке», которая решается простым жадным алгоритмом.
Там вырабатывают либо 0, либо значение в диапазоне [Pmin, Pmax].
Т.е. это не "непрерывная задача о рюкзаке" и симплекс-метод напрямую также не применим.
Представьте, что у газовых станций у всех Pmin = Pmax, тогда это классическая задача о рюкзаке.
А для такой задачи жадный алгоритм не подходит.
Здравствуйте, vsb, Вы писали:
vsb>Сильно в задание не вчитывался, если нет хитрой алгоритмики, то на Java HTTP API и WebSocket сделал бы на Spring дня за 3 (24 часа). За 40 минут я бы даже проект не настроил.
В .Net есть стандартный шаблон для вебсервиса сидящего в докере, так что тут надо только реализовать алогритм. Наверно за пару часов можно.
Здравствуйте, kaa.python, Вы писали:
L>>Нет смысла даже пытаться решать бессмысленную задачу. KP>Но ведь любое тестовое задание бессмысленное, так как если оно осмысленное, то возникают обвинения в попытке реализовать бизнес-логику на халяву.
С опытом все сложнее становится.
Слишком часто приходит задача с формулировкой "нам нужно семь перпендикулярных линий", а через две недели дознаний выясняется, что хотели покрасить входную дверь в синий цвет.
$>Да ладно. Там нужно прикрутить прикрутить оптимизационный solver (какой-нить minimax).
Там явно написано в условии, что готовые солверы не использовать. Если ты под солвером понимаешь какой-нибудь градиентный спуск из общедоступных библиотек, то такое, по идее, можно использовать. Вот только, как ты будешь целочисленность отдельных переменных обеспечивать?
$>За 24 часа можно уложиться- это часа 2-3 на почитать википедию, реализовать алгоритм и отладить еще 2-3 часа.
24 часа — это и есть 3-4 дня, внезапно. Ибо рвать жопу круглыми сутками никто в здравом уме не будет.
L>>Нет.
$>Если нужна работа и задачка намекает на интересные задачи в команде, то почему бы нет? Если жесткий лимит 40 минут, то я бы не стал начинать- без вариантов.
Мне жалко тратить несколько дней своей жизни на тестовое задание. И необходимости в поиске новой работы у меня сейчас нет (в последние несколько лет она меня находит).
Здравствуйте, Lexey, Вы писали:
L>Ветряки упаковывать не проблема, конечно. Вопрос, как остальные типы станций упаковывать, ибо они совсем не fixed cost/fixed energy.
Собственно, отсутствие граничных условий (количество станций и т.п.) — одна из проблем задачи. Всегда можно сказать, что "решение не верное, потому что мы предлагали другой контекст". Например, что ветряных станций не больше 10 (тогда перебор по подмножествам + жадный алгоритм будет самым оптимальным решением). Или наоборот, что ветряков будет очень много.
Реальность может давать еще больше разнообразия. Например, может оказаться, что производительность ветряков заметно меньше производительности других станций. Это может открыть дорогу к быстрым приближенным решениям. Т.е. считать секунду вместо 10 минут но давать ответ на 1-3% дороже в худшем случае.
Какой жесткий лимит? Сумасошол? Это тестовое задание, а не олимпиада. Тут никаких жестких лимитов быть не может, если работодателю нужны инженеры, а не студенты-олимпиадники.
$>Решается задачка уровня hard за 6 часов для чела, который не "вот прямо в этой предметной области сейчас".
Уровня hard чего? Хакерранка? Сколько задач такого уровня ты там решил?
$>Рынок работника, отсюда и уровень программистов в среднем как в Индии — там точно так же находит.
Не вижу никакой связи между "средней по больнице" и "своей температурой".
Здравствуйте, gandjustas, Вы писали:
G>Вы переоцениваете необходимость погружения в предметную область для разработки программ.
Есть области, в которых за понимание предметной области будут не кисло так доплачивать: бирживые торги, распознование образов чего-либо и тд.
У меня приятель занимался распознованием опухолей по снимкам томографии, под конец просветился в этой области не хуже врача.
Понятно, что есть аналитики, но если ты не разбираешься в теме, то беседа с аналитиком — это уже челенж. Если же, разбираешься в теме, то уже меньше тратишь время, хотя бы потому, что меньше спрашиваешь у аналитика.
Меньше багов, потому что аналитик забыл описать граничные условия, ты не знал о них, и все...
Здравствуйте, white_znake, Вы писали:
L>>Цели никого нанять не преследуют. _>Я может отстал от жизни и чего-то не понимаю, но если есть задание, то скорее всего его выдают желающим занять вакансию. Если есть вакансия, то должны быть и условия оплаты. _>Стартап — не исключение...
Внутренний стартап. Новое подразделение имеющейся компании.
Цели нанять не прослеживется. Какую цель преследует директор этого направления —
Здравствуйте, SkyDance, Вы писали:
G>>Симплекс метод за 40 минут? 99% программистов его не напишут вообще.
SD>На третьем (или четвертом?) курсе универа все писали.
Какого универа? И как это коррелирует с 99% программистов?
Здравствуйте, SkyDance, Вы писали:
SD>МГТУ им. Баумана.
А у нас его не писали, хотя и изучали весьма подробно.
SD>А 99% — это не программисты, а, ну, лучше не будем о грустном.
Тут я с тобой не соглашусь. Симплекс-метод — это больше математика, причем довольно специфическая, чем программирование. По способности его реализовать сложно делать выводы об уровне программиста.
Чего??
Такой наглой лжи на собеседовании я давно не слышал.
за 40 минут можно сделать, если с 3-го раза (имея идеальную память) ну или с 5-го раза для обычного человека. Т.е. окружение настроено, код помнишь почти наизусть, все движения отточены до автоматизма.
Я вот давеча делал тестовое задание типа библиотека для вычисления площади треугольника по трем сторонам.
с первого взгляда это фигня на 5 минут? минута на гугление формулы + 4 на код?
Ага, щас!
Пока поймешь какие проверки делать, пока выполнишь все проверки, пока тесты напишешь.
Проверка — это не только то что стороны должны быть положительны. И даже не то, что сумма двух сторон меньше третьей. Они не должны быть слишком большими, чтобы переполнения не вышло. Они не должны быть слишком маленькими, чтобы в результате ноль не вышел. Они не должны отличаться на много порядков, а то точность сильно потеряется. Они не должны быть очень-очень близкими к полупериметру, а то точность потеряется (или вообще ноль получим)
И тесты-тесты-тесыт (не забываем, речь идет о библиотеке которую могут использовать как угодно)
Результат — 2 часа. На площадь, мать его, треугольника.
В>Ну, и риторический вопрос — стали бы вы это делать?
Не-не-не.
Принципиально не делаю заданий расчитанных на несколько дней.
Сильно в задание не вчитывался, если нет хитрой алгоритмики, то на Java HTTP API и WebSocket сделал бы на Spring дня за 3 (24 часа). За 40 минут я бы даже проект не настроил.
Здравствуйте, Lexey, Вы писали:
L>Здравствуйте, Ватакуси, Вы писали:
В>>Мне сказали, что "обычно" выполняют за 40 минут.
L>"И вы говорите". L>В то, что алгоритм какой-нибудь сильный олимпиадник за 40 минут напишет, я могу поверить. Но, там кроме алгоритма еще вагон всякой мишуры будет.
Да ладно. Там нужно прикрутить прикрутить оптимизационный solver (какой-нить minimax). За 24 часа можно уложиться- это часа 2-3 на почитать википедию, реализовать алгоритм и отладить еще 2-3 часа.
L>Так что, реально тут работы на несколько дней, скорее всего.
В>>Ну, и риторический вопрос — стали бы вы это делать?
L>Нет.
Если нужна работа и задачка намекает на интересные задачи в команде, то почему бы нет? Если жесткий лимит 40 минут, то я бы не стал начинать- без вариантов.
Здравствуйте, Ватакуси, Вы писали:
В>Мне сказали, что "обычно" выполняют за 40 минут.
4-8 часов. Очень сильно зависит от алгоритма. Некоторые сложности есть в том, что нет граничных условий (т.е. сколько станций, максимально допустимое количество требуемой энергии и т.п.). В условиях их samples скорее всего будет динамическое программирование по Cost(количество требуемой энергии, используемые станции (только первая, первая-вторая, первая-вторая-третья и т.д.)). Из этого большая часть — на продумать/протестировать алгоритм. Если спешить и делать быстро — 40 минут максимум на алгоритм + 30 на обвязку (приложение), минимум автоматических тестов. Но это — олимпиадный режим. Неторопясь — от 2-х часов минимум.
Что входит в обвязку (и что я реально использую):
Многомодульный sbt project
Scala
Jetty server, старт и конфигурация кодом. Один handler
Своя json library в виде модуля
Парсинг данных в объекты, сериализация
fat jar build (sbt-assembly plugin)
Integration test в виде штатной sbt configuration.
Какие-нибудь первые интеграционные тесты на основе scalatest + java URLConnection (и небольшой обвязки, чтобы повторяющиеся вещи сделать более удобными). Конкретные тесты уже будут по ходу функциональности/алгоритма делаться если надо.
Это с нуля совершенно не торопясь делается максимум за час (включая поиск забытых ключиков в интернете). В этот же час можно написать короткую инструкцию о том, как запустить sbt assembly и выполнить java -jar. Если есть готовый проект-донор — 5-10 минут на все. Остальное — алгоритм и его тестирование.
В>Ну, и риторический вопрос — стали бы вы это делать?
В текущей ситуации — нет. Мне нужно книжку дописать сначала. И если я в состоянии думать, я лучше два часа потрачу на текст (за это время можно действительно много сделать), чем на решение задачки. Вот если бы у меня не было основной работы и был бы мой стек в вакансии — сделал бы.
Здравствуйте, Ватакуси, Вы писали:
В>Ну, и риторический вопрос — стали бы вы это делать?
Нет смысла даже пытаться решать бессмысленную задачу.
Во-первых, генерация ветроэлектростанций не зависит от наличия или отсутствия хотелок.
Во-вторых, регулирование мощности теплоэлектростанций возможно очень в небольших пределах. Даже работающая без нагрузки будет жрать топливо.
Здравствуйте, maxkar, Вы писали:
M>What? Решать дискретную задачу о рюкзаке минимаксом или оптимизационным solver'ом? Удачи
M>Если не понятно, откуда там рюкзак: Даем на вход все станции wind. Они fixed cost, fixed energy (после умножения на 10 — вся энергия в выводе — целые числа). Нужно их напаковать на суммарную энергию за минимум денег.
Автор задачки прямо написал, что они сами используют
For calculating the unit-commitment, we prefer you not to rely on an existing (linear-programming) solver but instead write an algorithm yourself.
Т.е. нужно сначала понять, какой solver подходит под эту задачу (и это может быть пример из учебника operation research), и накидать его на коленке из подручных материалов. Уровень "что нельзя использовать" тут непонятен- например, numpy можно использовать? Перемножение матриц вручную весьма медленное, но с numpy это влёт. Веб сервис с POST, надеюсь, тоже можно использовать готовые библиотеки.
Это же олимпиадная задача. Там нужно реализовать что-то типа решения задачи о рюкзаке.
Не олимпиадник конечно за 40 минут не выдаст такое решение. Олимпиадник вполне может.
Обвязка про докер и вебсокеты, а также хитрого вида входные данные, нужны чтобы чистых олимпиадников как раз отсеить.
Так что за 40 минут смогут единицы сделать.
Здравствуйте, maxkar, Вы писали:
M>What? Решать дискретную задачу о рюкзаке минимаксом или оптимизационным solver'ом? Удачи
Тут не совсем рюкзак, хотя что-то близкое. Ну и, приличные солверы умеют рюкзаки паковать.
M>Если не понятно, откуда там рюкзак: Даем на вход все станции wind. Они fixed cost, fixed energy (после умножения на 10 — вся энергия в выводе — целые числа). Нужно их напаковать на суммарную энергию за минимум денег.
Ветряки упаковывать не проблема, конечно. Вопрос, как остальные типы станций упаковывать, ибо они совсем не fixed cost/fixed energy.
В>>https://github.com/gem-spaas/powerplant-coding-challenge
В>>Мне сказали, что "обычно" выполняют за 40 минут. В>>Ну, и риторический вопрос — стали бы вы это делать?
_>Ну, сколько денег то корячится там?
За задание? Бесплатно.
Здравствуйте, Lexey, Вы писали:
L>Там явно написано в условии, что готовые солверы не использовать. Если ты под солвером понимаешь какой-нибудь градиентный спуск из общедоступных библиотек, то такое, по идее, можно использовать. Вот только, как ты будешь целочисленность отдельных переменных обеспечивать?
Я не верю в "за 40 минут придумать новый solver" и задача жизненная, значит всё уже придумали учёные до нас. Значит нужно найти алгоритм и закодить, а не просто вызвать этот алгоритм из готового пакета.
L>$>За 24 часа можно уложиться- это часа 2-3 на почитать википедию, реализовать алгоритм и отладить еще 2-3 часа.
L>24 часа — это и есть 3-4 дня, внезапно. Ибо рвать жопу круглыми сутками никто в здравом уме не будет.
Нет, 24 часа- это жёсткий лимит. Решается задачка уровня hard за 6 часов для чела, который не "вот прямо в этой предметной области сейчас".
L>необходимости в поиске новой работы у меня сейчас нет (в последние несколько лет она меня находит).
Рынок работника, отсюда и уровень программистов в среднем как в Индии — там точно так же находит.
Здравствуйте, $$, Вы писали:
L>>необходимости в поиске новой работы у меня сейчас нет (в последние несколько лет она меня находит).
$>Рынок работника, отсюда и уровень программистов в среднем как в Индии — там точно так же находит.
Задания как раз практикуют в странах где избыток разработчиков из Индии, так как они любят немного преувеличить в своих резюме
Здравствуйте, kaa.python, Вы писали:
KP>Задания как раз практикуют в странах где избыток разработчиков из Индии, так как они любят немного преувеличить в своих резюме
Как будто русские разработчики ничего не преувеличивают. Апликанты на позицию синьёра, с 3 годами опыта, начавшегося ещё во время института (тут это нонсенс)- из России.
$>Как будто русские разработчики ничего не преувеличивают. Апликанты на позицию синьёра, с 3 годами опыта, начавшегося ещё во время института (тут это нонсенс)- из России.
Там это нонсенс исключительно из-за тараканов в голове у австралов. У меня коллега в ЛК где-то за 3,5 года от стажёра до тимлида дошёл, на 100% заслуженно.
Я так понял что там симплекс-метод + рест-апи.
В>Ну, и риторический вопрос — стали бы вы это делать?
С ходу — наверно нет.
Но я на трудоустройство в их компанию и не рассчитываю.
Вероятно кто-то кто в предметную область погружен и имеер скилы, доки, наработки...
$>Автор задачки прямо написал, что они сами используют
А мне кажется, что они очень прозрачно попросили не забивать шурупы микроскопом. И что не надо усложнять решение и искать в заведомо неверных направлениях.
Мне вот казалось, что я очень прозрачно намекнул на простой факт. Видимо — нет. Задача о рюкзаке — частный случай задачи о ветряках. Задача о рюкзаке — NP-полная. Типичный линейный solver (тот же симплекс-метод) — полиномиальный. Вывод — взять "линейный солвер" и прикрутить его напрямую к (NP-полной) задаче — пусть безнадежный. Нужно будет усложнять. Но многие разработчики не видят классов сложности, поэтому авторы пытались облегчить задачу и закрыть заведомо бесперспективные направления.
$>Уровень "что нельзя использовать" тут непонятен- например, numpy можно использовать?
Можно. Она ну никак не поможет побороть сложность (complexity class) исходной задачи. Более того, чтобы выбрать правильную библиотеку нужно хорошо понимать ее ограничения и особенности (например, псевдополиномиальные решения или осбоенности экспоненциального перебора). Обычно люди, имеющие такое знание, неплохо знают и основы (базовые блоки). Написать реализацию частного случая (простого!) для них будет легко.
$>Я не верю в "за 40 минут придумать новый solver" и задача жизненная, значит всё уже придумали учёные до нас. Значит нужно найти алгоритм и закодить, а не просто вызвать этот алгоритм из готового пакета.
Почему нельзя? Я же придумал Обычно из готовых алгоритмов можно легко собрать, особенно зная, что есть решение.
Я бы не был очень оптимистичен по поводу поиска с учетом их "do not use". Вполне может оказаться, что "массовые" решалки плохо ведут себя на их задаче. А чтобы найти хороший solver, нужно быть в теме (читать статьи, иметь специализированное образование и т.п.). Кто вообще сказал, что рядовой программист должен быть способен решить эту задачу? Может, они раньше нанимали и поняли, что ничего хорошего не получается. И теперь ищут людей, для которых придумать новый специализированный solver за 40 минут — совсем не проблема.
Здравствуйте, 3V,
3V>Я так понял что там симплекс-метод + рест-апи.
Симплекс метод за 40 минут? 99% программистов его не напишут вообще.
Я может невнимательно читал, но на вид это «непрерывная задача о рюкзаке», которая решается простым жадным алгоритмом.
3V>Вероятно кто-то кто в предметную область погружен и имеер скилы, доки, наработки...
Вы переоцениваете необходимость погружения в предметную область для разработки программ.
Здравствуйте, Lazytech, Вы писали:
L>Согласен. Вообще, насколько я понял, дело не в багах. Просто человек отлично разбирается в картах и в целом умеет ориентироваться на местности.
В первую очередь, именно баги. В частности, чтобы проходить сквозь стены.
Здравствуйте, Codealot, Вы писали:
C>В первую очередь, именно баги. В частности, чтобы проходить сквозь стены.
Он вроде не проходил сквозь стены. Человек просто наловчился делать ступеньки выстрелами из клеевой пушки и взбираться по этим ступенькам на расположенный выше этаж.
Ну и пусть продолжают искать тех, кто выполнит за 40 минут.
Это похоже на развод, когда искал первую работу, тоже было:
— "Ты типа молодец, тестовое задание выполнил, но "обычно" его делают за 1 час, а ты выполнил за 2,3,4,...N часов".
— "Так... Ты хочешь ЗП — N... Но понимаешь, ты же сделал задание за большее время, поэтому ты недостоен ЗП — N, мы можем предложить только M, где M < N".
Если не секрет, то какую ЗП предлагают? По названию компании искать — влом.
L>Судя по описанию, на гитхабе, это "внтуренний" стартап. L>Цели никого нанять не преследуют.
Я может отстал от жизни и чего-то не понимаю, но если есть задание, то скорее всего его выдают желающим занять вакансию. Если есть вакансия, то должны быть и условия оплаты.
Стартап — не исключение...
В>Мне сказали, что "обычно" выполняют за 40 минут.
Имхо, они там не зря про merit order упомянули.
Если не заморачиваться с алгоритмикой, то можно посчитать этот самый merit как стоимость производства 1 MW энергии.
Отсортировать заводы по возрастанию merit.
И пройти по отсортированному списку, накидывая в результат заводы с учетом требуемой P, Pmin/Pmax и wind(%).
Мне кажется это максимум, что можно выдать на собеседовании за 20-30 минут без предварительной подготовки.
В>Ну, и риторический вопрос — стали бы вы это делать?
Если бы хотел конкретно в эту компанию, то сделал бы.
В>Мне сказали, что "обычно" выполняют за 40 минут. В>Ну, и риторический вопрос — стали бы вы это делать?
Прочесть и понять постановку задачи, написать письмо с дополнительными вопросами по задаче, ждать ответа — 1 день.
Прочесть ответ, обдумать задачу еще раз, продумать алгоритм, набросать прототип, написать новое письмо с вопросами по задаче, ждать ответа — 1 день.
Прочесть ответ, начать писать код (готовность 50%), написать письмо с уточняющими вопросами, ждать ответ — 1 день.
Прочесть ответ, переделать половину написанного кода, дописать отстаток(готовность 95%) — 1 день.
Дописать код, написать тесты, убрать мусор, добавить комментарии, все еще раз проверить, отправить результат — 4 часа.
Прочесть ответ аналитика, обдумать, внести исправления, отправить результат 4 часа.
Итого: 5 дней или рабочая неделя.
Или делаю хорошо и основательно(за деньги, естественно) или не делаю совсем.
Здравствуйте, Codealot, Вы писали:
C>В первую очередь, именно баги. В частности, чтобы проходить сквозь стены.
Это категория any%. Емнип там разрешено всё кроме консольных команд.
Если хочешь норм, то ищи 100% спидраны.
Здравствуйте, RushDevion, Вы писали:
RD>Мне кажется это максимум, что можно выдать на собеседовании за 20-30 минут без предварительной подготовки.
Это и есть правильное решение.
Здравствуйте, StatujaLeha, Вы писали:
SL>Здравствуйте, gandjustas, Вы писали:
G>>Симплекс метод за 40 минут? 99% программистов его не напишут вообще. G>>Я может невнимательно читал, но на вид это «непрерывная задача о рюкзаке», которая решается простым жадным алгоритмом.
SL>Там вырабатывают либо 0, либо значение в диапазоне [Pmin, Pmax]. SL>Т.е. это не "непрерывная задача о рюкзаке" и симплекс-метод напрямую также не применим.
Это очень похоже на нее.
SL>Представьте, что у газовых станций у всех Pmin = Pmax, тогда это классическая задача о рюкзаке. SL>А для такой задачи жадный алгоритм не подходит.
Конечно не подходи в исходном варианте, иначе было бы слишком просто.
Но его легко модифцироват.
На каждом шаге проверяем если оставшийся load меньше чем Pmin следующего элемента, то рассматриваем два варианта
а) взять текущий элемент в рюкзак и получить оставшийся load из элементов списка после следующего
б) игнориовать текущий элемент и попробовать забить рюкзак из оставшихся.
Из двух вариантов выбрать где стоимость меньше.
Я думаю такую простую рекурсию за 40 минут можно осилить.
Здравствуйте, gandjustas, Вы писали:
G>Это очень похоже на нее.
Так задача целочисленного линейного программирования тоже "похожа" на задачу обычного линейного программирования.
Только при ведении требования на целочисленность решений внезапно задача становится NP-complete.
G>Но его легко модифцироват.
G>На каждом шаге проверяем если оставшийся load меньше чем Pmin следующего элемента, то рассматриваем два варианта G>а) взять текущий элемент в рюкзак и получить оставшийся load из элементов списка после следующего G>б) игнориовать текущий элемент и попробовать забить рюкзак из оставшихся. G>Из двух вариантов выбрать где стоимость меньше.
Не понял толком алгоритм, потому что не написано, что делать, если оставшийся load больше, чем Pmin следующего элемента.
И еще правило сортировки не указано: сортировка по Pmin может отличаться от сортировки по Pmax.
Допустим, у нас есть:
1. Газовые станции [[5, 10], [35, 40], [35, 40], [35, 40], [55, 60], [75, 80]]
2. Керосиновая станция: [0, 100]
Надо набрать мощность 231.
Чего получим по алгоритму?
G>Я думаю такую простую рекурсию за 40 минут можно осилить.
Думаю, она уже будет с экспоненциальным ростом.
Вам могут выдать набор из 666 станций и сказать, что ответят, когда программа завершит работу
Еще, как я понял, ветряки имеют цену генерации ноль, но генерят строго определенную мощность.
Т.е. у них Pmin = Pmax.
Получается, что сначала надо решить классическую задачу о рюкзаке на множестве ветряков.
Здравствуйте, StatujaLeha, Вы писали:
SL>Здравствуйте, gandjustas, Вы писали:
G>>Это очень похоже на нее.
SL>Так задача целочисленного линейного программирования тоже "похожа" на задачу обычного линейного программирования. SL>Только при ведении требования на целочисленность решений внезапно задача становится NP-complete.
Кстати если внимательно прочитать условия, то там написано что
The power produced by each powerplant has to be a multiple of 0.1 Mw and the sum of the power produced by all the powerplants together should equal the load.
То есть это NP-полная задача, которая сводится к задаче о рюкзаке.
Только написать без подготовки решение задачи о рюкзаке за 40 минут — маловероятно.
Здравствуйте, SkyDance, Вы писали:
G>>Симплекс метод за 40 минут? 99% программистов его не напишут вообще.
SD>На третьем (или четвертом?) курсе универа все писали.
Линейное программирование это ж экономика. Инженеры (типо меня) так вообще совсем не слышали про это в институте.
Здравствуйте, gandjustas, Вы писали:
G>Кстати если внимательно прочитать условия, то там написано что G>
G>The power produced by each powerplant has to be a multiple of 0.1 Mw and the sum of the power produced by all the powerplants together should equal the load.
G>То есть это NP-полная задача, которая сводится к задаче о рюкзаке.
Да, согласен.
Это условие трансформирует задачу.
1. Есть n кучек, в каждой из них есть предметы определенного веса [Pmin, Pmin + 0.1, ..., Pmax].
2. Надо наполнить рюкзак, взяв из каждой кучки не более одного предмета.
Подумал, погуглил, пока не вижу, как она сводится к классической задаче о рюкзаке...
Видимо, тут еще что-то.
Здравствуйте, StatujaLeha, Вы писали:
SL>Подумал, погуглил, пока не вижу, как она сводится к классической задаче о рюкзаке... SL>Видимо, тут еще что-то.
Выглядит так, как будто можно отсортировать по возрастанию цены на 0.1 мощности, каждому "предмету" сопоставить Pmin и Pmax и рассчитывать суммы "взятых" Pmin и Pmax. Допустимыми будут те решения, для которых Pmin <= P <= Pmax. А вот оптимальное, похоже, придется искать полным перебором с отсечением вариантов, которые точно будут хуже, чем текущее лучшее решение.
Здравствуйте, SkyDance, Вы писали:
L>>Какого универа? И как это коррелирует с 99% программистов?
SD>МГТУ им. Баумана.
SD>А 99% — это не программисты, а, ну, лучше не будем о грустном.
Максим, ещё раз- линейное программирование это об экономике. Логистика, составление портфелей акций. Все математики это проходят. Насчёт всех программистов я хз- может проходят, но не понимают.
За тебя я не сомневаюсь, ты вроде и без Бауманки занимал места в олимпиадах.
Здравствуйте, Ip Man, Вы писали:
KP>>В Гонконге тоже принято гномами развлекаться?
IM>в топовых компаниях — однозначно
Кстати, а у вас сейчас компании не побежали с острова? Я когда-то думал переехать в Гонконг, но судя по новостям это стало не целесообразно. Или нагнетают просто?