Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 35
Если городов ОЧЕНЬ много, ответ мог бы быть такой.
Пять-факториал — это совсем немного. Так что берём 120-местный массив и заполняем, сколько голосов отдано каждому из 120 вариантов. А затем уже проходом по этому массиву выясняем, кто победитель, макс. 120^2.
Если городов мало (до 100), вероятно, ваш (лобовой) ответ действительно лучший.
Пять-факториал — это совсем немного. Так что берём 120-местный массив и заполняем, сколько голосов отдано каждому из 120 вариантов. А затем уже проходом по этому массиву выясняем, кто победитель, макс. 120^2.
Если городов мало (до 100), вероятно, ваш (лобовой) ответ действительно лучший.
Для тех, кто легко справился с этой задачей, хочу предложить еще одну, которая когда-то мне очень понравилась.
Есть N ящиков. Для каждого ящика известены w и p.
где:
w — вес ящика.
p — вес который способен выдержать ящик не будучи раздавленным
(вес ящика(ов), который можно поставить на него).
Задача — построить башню из ящиков максимальной высоты.
Есть N ящиков. Для каждого ящика известены w и p.
где:
w — вес ящика.
p — вес который способен выдержать ящик не будучи раздавленным
(вес ящика(ов), который можно поставить на него).
Задача — построить башню из ящиков максимальной высоты.
Почему-то напомнило задачу про монеты, суть сводится к следующему:
Есть монеты номиналом N1...Nk.
Надо узнать, можно ли этими монетами набрать сумму M.
Но возвращаясь к ящикам, я пока представляю только способ решения «в лоб», полным перебором…
Есть монеты номиналом N1...Nk.
Надо узнать, можно ли этими монетами набрать сумму M.
Но возвращаясь к ящикам, я пока представляю только способ решения «в лоб», полным перебором…
Очень бы хотелось услышать решения, альтернативные моему.
(это не полный перебор)
(это не полный перебор)
Это задача сводится к задаче о камнях. (Есть n камней с массами M1,…, Mn нужно сказать, можно ли их разложить на 2 кучки равной массы)
Известно что это NP полная задача. NP полная означает, что если вы найдёте для неё полиномиальное решение (т.е. не полный перебор), то вы докажете что P = NP, тем самым решите одну из важнейших задач человечества)
Могу сразу сказать, что почти все учёные принимают на веру что P != NP. Только не знают как доказать. Так что, в принципе, полиномиального решения вы не найдёте. Можете не ломать голову)
Известно что это NP полная задача. NP полная означает, что если вы найдёте для неё полиномиальное решение (т.е. не полный перебор), то вы докажете что P = NP, тем самым решите одну из важнейших задач человечества)
Могу сразу сказать, что почти все учёные принимают на веру что P != NP. Только не знают как доказать. Так что, в принципе, полиномиального решения вы не найдёте. Можете не ломать голову)
Хотя вот интересная мысль пришла в голову:
Решаем с помощью мультиграфа.
У нас есть N вершин, каждый ящик — вершина.
На 1м этам мы соединяем дугами только те ящики, которые могут выдержать друг друга, т.е. если ящик i выдерживает ящик j, то такая дуга есть. Каждую дугу мы при этом маркируем уникальным номером.
На 2м этапе мы добавляем те дуги, цепочки которых нам позволят выдержать высоту в 2 ящика (вершины i->j->k), при этом мы эти 2 дуги (i->j и j->k) маркируем одним номером.
На 3м — по аналогии, получаем цепочки, способные выдержать высоту 3 ящика (все дуги имеют один номер).
И так далее, пока не окажется, что на следующем шаге мы теряем все дуги.
Полученные цепочки с одним номером дуг и будут нашими башнями.
Осталось рассмотреть частные случае, вроде когда из 1й цепочки получается 2 и более (скажем, на 2 ящика можно поставить 3м еще 2 разных ящика).
Но в этом случае мы можем записать обе цепочки длиной 3 независимо друг от друга.
В 1м приближении решение выглядит так. Завтра может дополню изображениями.
Решаем с помощью мультиграфа.
У нас есть N вершин, каждый ящик — вершина.
На 1м этам мы соединяем дугами только те ящики, которые могут выдержать друг друга, т.е. если ящик i выдерживает ящик j, то такая дуга есть. Каждую дугу мы при этом маркируем уникальным номером.
На 2м этапе мы добавляем те дуги, цепочки которых нам позволят выдержать высоту в 2 ящика (вершины i->j->k), при этом мы эти 2 дуги (i->j и j->k) маркируем одним номером.
На 3м — по аналогии, получаем цепочки, способные выдержать высоту 3 ящика (все дуги имеют один номер).
И так далее, пока не окажется, что на следующем шаге мы теряем все дуги.
Полученные цепочки с одним номером дуг и будут нашими башнями.
Осталось рассмотреть частные случае, вроде когда из 1й цепочки получается 2 и более (скажем, на 2 ящика можно поставить 3м еще 2 разных ящика).
Но в этом случае мы можем записать обе цепочки длиной 3 независимо друг от друга.
В 1м приближении решение выглядит так. Завтра может дополню изображениями.
В фразе «Осталось рассмотреть частные случаи, вроде когда из 1й цепочки получается 2 и более» и кроется сложность задачи.
А если из одной цепочки получается 10 или более? и так на каждом шаге?
Представьте, что у вас 100 ящиков. Их вес колеблется от 1 до 10, а грузоподъемность от 100 до 200. Тогда получится, что башню высоты 10 можно построить из любых 10 ящиков, а это даст C(m,n) башен при n=100, m=10
Подсказок давать не буду. Но мне задача понравилась
А если из одной цепочки получается 10 или более? и так на каждом шаге?
Представьте, что у вас 100 ящиков. Их вес колеблется от 1 до 10, а грузоподъемность от 100 до 200. Тогда получится, что башню высоты 10 можно построить из любых 10 ящиков, а это даст C(m,n) башен при n=100, m=10
Подсказок давать не буду. Но мне задача понравилась
Согласен, решение — один из вариантов полнопереборного алгоритма. Его можно сравнить с обходом графа решений в ширину, в то время как рекурсивный алгоритм перебора — обход в глубину.
К сожалению, в задаче есть некоторая детерминированность — если возможны 2 разных ответа, то по условию можно вывести только 1 вариант.
Если же нам надо вывести все возможные варианты — то в Вашем же примере так или иначе придется полностью перебрать все варианты.
К сожалению, в задаче есть некоторая детерминированность — если возможны 2 разных ответа, то по условию можно вывести только 1 вариант.
Если же нам надо вывести все возможные варианты — то в Вашем же примере так или иначе придется полностью перебрать все варианты.
Задача легко решается за O(N^2)
Добавим к p для каждого ящика его w. Теперь несложно доказать (но мне влом писать), что существует оптимальная башня в которой ящики идут сверху вниз в порядке возрастания p. Теперь посчитаем следующую динамику — какой наименьший вес имеет башенка из i ящиков если ящики можно выбирать из j первых. Пересчет очевиден.
Добавим к p для каждого ящика его w. Теперь несложно доказать (но мне влом писать), что существует оптимальная башня в которой ящики идут сверху вниз в порядке возрастания p. Теперь посчитаем следующую динамику — какой наименьший вес имеет башенка из i ящиков если ящики можно выбирать из j первых. Пересчет очевиден.
Ваша предпосылка:
не верна. Контрпример:
Я дал ссылку на статью в википедии. Посмотрите пункт «Задача о ранце с возможностью единичного выбора предмета». Примите стоимость предмета за 1. Добавляется дополнительное сравнение веса уже выбранных ящиков с P текущего ящика.
egork:
существует оптимальная башня в которой ящики идут сверху вниз в порядке возрастания p
не верна. Контрпример:
p 4 4 5 6 7 w 6 1 1 1 1
Я дал ссылку на статью в википедии. Посмотрите пункт «Задача о ранце с возможностью единичного выбора предмета». Примите стоимость предмета за 1. Добавляется дополнительное сравнение веса уже выбранных ящиков с P текущего ящика.
а вы заметили, что я к p прибавил w?
И да, задача о рюкзаке, где ценность всех предметов 1 — вполне себе решается :)
И да, задача о рюкзаке, где ценность всех предметов 1 — вполне себе решается :)
Само собой.
а вы заметили, что я к p прибавил w?
Вам следует ясней выражаться. Но вы правы. Ящики в оптимальной последовательности действительно будут расположены в порядке неубывания p+w (и в порядке неубывания p внутри групп с одинаковым p+w). Доказывается это действительно легко, по индукции. Ваше решение верное, и оно подтверждает утверждение, что эта задача является частным случаем задачи о рюкзаке.
В общем, вы молодец, поздравляю.
Все верно.
Сначала сортируем ящики по (p+w), затем динамикой получаем самое большое подмножество — это и будет ответ.
Доказательство не сложное — желающие могут потренироваться.
Сначала сортируем ящики по (p+w), затем динамикой получаем самое большое подмножество — это и будет ответ.
Доказательство не сложное — желающие могут потренироваться.
Ну я бы решал ее методом динамического программирования — рекурсия с запоминанием (кэшем).
Для каждого ящика ищем максимальную цепочку ящиков над ним с помощью рекурсии, и потом выбираем самую длинную. Алгоритм будет быстрый так как уже вычисленные данные будут просто в памяти.
Для каждого ящика ищем максимальную цепочку ящиков над ним с помощью рекурсии, и потом выбираем самую длинную. Алгоритм будет быстрый так как уже вычисленные данные будут просто в памяти.
Автор, извините, но мне ваша статья не понравилась. Заходя под кат я надеялся увидеть или сложную, действительно «олимпиадную» задачку, или простую задачку, но с неординарным решением, в общем, хоть что-то. В результате получил простую задачу решённую очевидным способом «в лоб». Возможно, я не прав, но что тогда вы хотели донести до читателей?
Не очень понятны качественные критерии решения. Чтобы в принципе работало? Ограничений на память и количество проходов нет?
Тогда очень простое в отладке и однозначное решение, хоть и объемное.
Поскольку данные упорядочены и по условию всегда фаворит, делаем хеш-массив [пара => сколько раз встречалось]. Т.е. ( r/P => 5, o/S => 3 ) и т.п.
Затем сформировать массив самых частотных сочетаний, только чтобы первая буква была уникальной. Это будет идеальная расстановка.
По каждому городу функция близости к идеальной расстановке — сколько из идеальных сочетаний нашлось в данном городе.
Опять же, помня, что есть явный фаворит из условия и возможность прочитать все в память и несколько раз пройти. Сейчас накидал решение на php — совпадает. Еще тестовые данные есть? :)
Тогда очень простое в отладке и однозначное решение, хоть и объемное.
Поскольку данные упорядочены и по условию всегда фаворит, делаем хеш-массив [пара => сколько раз встречалось]. Т.е. ( r/P => 5, o/S => 3 ) и т.п.
Затем сформировать массив самых частотных сочетаний, только чтобы первая буква была уникальной. Это будет идеальная расстановка.
По каждому городу функция близости к идеальной расстановке — сколько из идеальных сочетаний нашлось в данном городе.
Опять же, помня, что есть явный фаворит из условия и возможность прочитать все в память и несколько раз пройти. Сейчас накидал решение на php — совпадает. Еще тестовые данные есть? :)
Проверка проводится по ряду тестов на сервере. Есть ограничение по времени работы программы (3 секунды), ну и наверное ограничение на память, хотя в условии об этом не говорится. Эта задача действительно достаточно простая, поэтому тут трудно превысить лимит времени или памяти. Здесь важно учесть все возможные подводные камни.
Рекомендую вам свое решение перекинуть на C++, java или Pascal и отнести на проверку, сразу станет ясно насколько оно удачно.
Рекомендую вам свое решение перекинуть на C++, java или Pascal и отнести на проверку, сразу станет ясно насколько оно удачно.
А вот не нужно каждый город с остальными сравнивать, ибо это сложность O(n^2).
Достаточно заполнить матрицу 5х5, где строчки будут — цвета корзин, а столбцы — типы отходов. На пересечении целое число — кол-во городов, в которых в N'ом цвете корзины M'тый тип отходов.
Заолняется матрица за линейное время, отличия в городе по ней считаются тоже линейно (О(n)).
Достаточно заполнить матрицу 5х5, где строчки будут — цвета корзин, а столбцы — типы отходов. На пересечении целое число — кол-во городов, в которых в N'ом цвете корзины M'тый тип отходов.
Заолняется матрица за линейное время, отличия в городе по ней считаются тоже линейно (О(n)).
Автор, давай что-нибудь на динамическое программирование, чтобы на самом деле мозги размять)
Спасибо, задача несложная, но интересно было :) Решил вторым способом.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Олимпиадное хобби. Задача об утилизации отходов