Можно находить точно быстрее, чем за O(2n), используя идею Meet In The Middle, за O(2n/2logn), используя O(2n/2) памяти. То есть n=50 жует не задумываясь.
Идея простая как валенок: Берем половину предметов, для всех их подмножеств находим стоимости, записываем их в массив и сортим по суммарному размеру. Для каждого префикса массива находим макс. стоимость. Потом перебираем вторую половину и для каждого его подмножества ищем бинарным поиском в массиве префикс всех подмножеств второй половины, который еще «влазит» в рюкзак и смотрим максимальную стоимость по ним. Иии… вроде бы все.
Планируются. Но сначала хотя бы под Windows надо допилить)
На Manufactoria игра похожа только внешне, на самом деле игровая механика сильно различается.
Сходство случайно — о Manufactoria я узнал только когда уже сделал первую демку.
Пишу подобную игру «для программистов», к концу месяца надеюсь релизнуть.
Игра называется Great Permutator.
Посмотреть описание и скачать демо можно здесь.
+Еще видео летсплея можно посмотреть тут.
Игра писалась, собственно, под впечатлением от SpaceChem и LightBot.
Всмысле? Ткните мне переменную, которая используется без инициализации.
Глобальные переменные по умолчанию инициализируются нулями. Из стандарта:
«Objects with static storage duration (3.7.1) shall be zero-initialized (8.5) before any other initialization takes place.»
В остальных переменных, конечно же, по умолчанию мусор. Однако каждой из этих переменных всегда присваивается не мусорное значение до того, как значение этой переменной будет где либо использовано. Или так делать нельзя? Если да, то почему?
Не думал, что заберусь так высоко. Наверно мне повезло с тестами (у меня не монотонно возрастает время работы с ростом n) — на худшем для меня тесте мое решение работает 0.6 с на моей машине.
Суть решения описана в комментарии в самом решении. Если подробно — тупое блочное решето, вообще без оптимизаций, почти идентичное реализации с e-maxx. Всего блоков получилось порядка 7000, с шагом в 350 блоков я предпосчитал ответы. Теперь для первых 350*x блоков ответ берем из таблицы, а для оставшихся не более чем 350 блоков досчитываем блочным решетом.
Все константы подобраны эмпирически.
Думаю, у других топовых решений что то подобное и страшный текст кракозябрами — это просто сжатые предпросчитанные ответы.
Мое решение можно было еще соптимизировать мелкими оптимизациями (ускорение раза в 2-3), но я особо не заморачивался. К сожалению, новый год встретил с насморком и температурой и на всякие извращения уже не было сил.
Идея простая как валенок: Берем половину предметов, для всех их подмножеств находим стоимости, записываем их в массив и сортим по суммарному размеру. Для каждого префикса массива находим макс. стоимость. Потом перебираем вторую половину и для каждого его подмножества ищем бинарным поиском в массиве префикс всех подмножеств второй половины, который еще «влазит» в рюкзак и смотрим максимальную стоимость по ним. Иии… вроде бы все.
Но как-то изначально повелось считать именно количество строк…
На Manufactoria игра похожа только внешне, на самом деле игровая механика сильно различается.
Сходство случайно — о Manufactoria я узнал только когда уже сделал первую демку.
Пишу подобную игру «для программистов», к концу месяца надеюсь релизнуть.
Игра называется Great Permutator.
Посмотреть описание и скачать демо можно здесь.
+Еще видео летсплея можно посмотреть тут.
Игра писалась, собственно, под впечатлением от SpaceChem и LightBot.
Глобальные переменные по умолчанию инициализируются нулями. Из стандарта:
«Objects with static storage duration (3.7.1) shall be zero-initialized (8.5) before any other initialization takes place.»
В остальных переменных, конечно же, по умолчанию мусор. Однако каждой из этих переменных всегда присваивается не мусорное значение до того, как значение этой переменной будет где либо использовано. Или так делать нельзя? Если да, то почему?
Не думал, что заберусь так высоко. Наверно мне повезло с тестами (у меня не монотонно возрастает время работы с ростом n) — на худшем для меня тесте мое решение работает 0.6 с на моей машине.
Суть решения описана в комментарии в самом решении. Если подробно — тупое блочное решето, вообще без оптимизаций, почти идентичное реализации с e-maxx. Всего блоков получилось порядка 7000, с шагом в 350 блоков я предпосчитал ответы. Теперь для первых 350*x блоков ответ берем из таблицы, а для оставшихся не более чем 350 блоков досчитываем блочным решетом.
Все константы подобраны эмпирически.
Думаю, у других топовых решений что то подобное и страшный текст кракозябрами — это просто сжатые предпросчитанные ответы.
Мое решение можно было еще соптимизировать мелкими оптимизациями (ускорение раза в 2-3), но я особо не заморачивался. К сожалению, новый год встретил с насморком и температурой и на всякие извращения уже не было сил.