Во-первых, вы сможете решить эту задачу, если с ней столкнётесь. Ведь SergeyACTIVITI в своём посте говорил лишь о удобной обёртке на питоне. Кроме того, этот алгоритм можно модифицировать. Кем-то написаный решатель решает лишь ограниченный круг задач, который в него заложен. А вы можете модифицировать алгоритм для любой ситуации.
Конечно, это самая естественная мысль, но, к сожалению, неверная.
Допустим, ёмкость рюкзака равна 6. И есть два типа вещей: у первого объём 4 и стоимость 5, у второго — объём 3 и стотимость 3. Согласно Вашему алгоритму, мы возьмём одну вещь первого типа, и всё. Стоимость взятого — 5. А можно взять две вещи второго типа, стоимость — 6.
Да, но и не только. Я предполагаю, что есть люди, которым алгоритмы интересны не настолько, чтобы специально этим интересоваться, но которые будут рады, если им что-нибудь интересное на эту тему расскажут.
Да и, кроме того, интересных и полезных алгоритмов существует столько, что, чтобы всех их знать, надо интересоваться этим очень и очень сильно.
То есть, вы предпочли бы видеть такие статьи в более научном и серьёзном виде?
Вы исходите из ложной предпосылки о том, что всех можно разделить строго на две категории.
А я исхожу из комментариев к посту, ссылка на который содержится в теле этого поста.
Всё же, надо заметить, что в математике дерево — это связный граф без циклов. И два дерева (собственно, как и просто два графа) считаются изоморфными, если можно пронумеровать вершины обоих так, что если вязть два номера, то вершины под этими номера одновременно соединены или не соединены ребром в обоих деревьях (графах). Поэтому 2, 3 и 4 деревья у Вас на рисунке — изоморфны, т.е., неразличимы с точки зрения теории графов.
Поэтому имеет смысл уточнить, что здесь считается произвольным деревом.
Что значит, для чего? Он просто не точный. Прогрешность хуже, чем одна наносекунда.
вы вообще читать умеете? Цитата из моего коммента:
«значит, нужно делать много раз каждый тест, и, желательно, много тестов»
Чтобы была нормальная точность, надо делать каждый тест много раз — по моему опыту, миллион даже будет маловато, 10 млн минимум. А то я уже получал какие-то фантастические результаты замеров времени, когда делал 1 000 000 тестов, и время измерялось в милисекундах. А потом всё становилось на свои места, когда я увеличивал количество тестов до миллиарда.
А для репрезентативности выборки надо делать много разных тестов. Вот и получается, что надо делать много раз по секунде.
Замечание в целом верное (когда речь касается промышленного программирования, а не олимпиадного), но сразу замечу, что вопрос исследовался скорее из интереса, нежели для пользы дела.
Если же говорить о деле, то изредка всё же лучше писать своё, даже если возможно использовать стандартный метод — и для этой цели в статье в некоторой степени исследован вопрос о том, в каких случаях какой метод лучше применить.
Читайте полностью: «java не очень точна, когда меряешь маленькое время». Имеется в виду, что System.nanoTime(), который я использовал, выдаёт неточный результат. И чем меньше время, которое пытаешься с его помощью померять, тем больше относительная погрешность.
СПбГУ, по-моему, ежегодно команд семнадцать посылает на четвертьфинал) Но, надо честно признать, смысл участвовать есть командам десяти, максимум (сужу по последнему четвертьфиналу).
На работу не берут тех олимпмиадников, которым кажется, что олимпиадных навыков и знаних вполне хватит для промышленного программирования. А при прочих равных опыт в спотривном программирование является сильным бонусом во многих местах. Мне сейчас, например, сильно помогает то, что я пишу практически без ошибок, а баги (не только свои) могу искать без тестинга — просто внимательным чтением кода. Что очень приятно, особенно когда тестинг невозможен или затруднён =)
Ну и вообще, олимпиды дают много полезных навыков. Просто не надо забывать, что для работы нужны ещё кое-какие навыки, которых олимпиады не дают.
Лично знаком с командой, которая абсолютно не занималась спортивным программированием в школе, а на третьем курсе уже была серебрянным призёром финала.
Спасибо, полезная идея!
Замечу, что если надо найти только конечный результат, но не путь, то эта идея позволяет сэкономить память, оставив время таким же.
Допустим, ёмкость рюкзака равна 6. И есть два типа вещей: у первого объём 4 и стоимость 5, у второго — объём 3 и стотимость 3. Согласно Вашему алгоритму, мы возьмём одну вещь первого типа, и всё. Стоимость взятого — 5. А можно взять две вещи второго типа, стоимость — 6.
Да и, кроме того, интересных и полезных алгоритмов существует столько, что, чтобы всех их знать, надо интересоваться этим очень и очень сильно.
То есть, вы предпочли бы видеть такие статьи в более научном и серьёзном виде?
А я исхожу из комментариев к посту, ссылка на который содержится в теле этого поста.
Поэтому имеет смысл уточнить, что здесь считается произвольным деревом.
вы вообще читать умеете? Цитата из моего коммента:
«значит, нужно делать много раз каждый тест, и, желательно, много тестов»
Чтобы была нормальная точность, надо делать каждый тест много раз — по моему опыту, миллион даже будет маловато, 10 млн минимум. А то я уже получал какие-то фантастические результаты замеров времени, когда делал 1 000 000 тестов, и время измерялось в милисекундах. А потом всё становилось на свои места, когда я увеличивал количество тестов до миллиарда.
А для репрезентативности выборки надо делать много разных тестов. Вот и получается, что надо делать много раз по секунде.
Если же говорить о деле, то изредка всё же лучше писать своё, даже если возможно использовать стандартный метод — и для этой цели в статье в некоторой степени исследован вопрос о том, в каких случаях какой метод лучше применить.
Ну и вообще, олимпиды дают много полезных навыков. Просто не надо забывать, что для работы нужны ещё кое-какие навыки, которых олимпиады не дают.
Замечу, что если надо найти только конечный результат, но не путь, то эта идея позволяет сэкономить память, оставив время таким же.