Загадка google про рюкзак
Обновлено: 04.11.2024
Пару лет назад столкнулся с так называемой задачей о рюкзаке на одном из собеседований, нашел быстренько решение в интернете. Попытался разобрать и. ничего не понял. Кое как поменял названия переменных, а кто так не делает когда находит готовое решение для home таски? Отправил и забыл как страшный сон. Недавно друг скинул подобную задачу про монеты и в этот раз я уже быстренько разобрался с этой когда то, как казалось мне неподъемной задачкой.
Хотел бы отметить книгу Grokking Algorithms автора Aditya Bhargava. У нее прям максимально простым языком расписаны основы алгоритмов. Так что если, вы как и я в универе думали что алгоритмы вам никогда не пригодятся, потому что FAANG это не для вас. То я вас и разочарую и обрадую, попасть туда может каждый, если конечно приложит достаточно усилий, ну а разочарую тем что вам конечно придется поднапрячься и осилить алгоритмы и чем раньше вы начнете это делать, тем лучше.
Собственно задача, одна из популярных её вариаций. Вор пробрался в ювелирный магазин, у него есть рюкзак объемом 4 единицы. В магазине, он увидел три вещи:
Вещи которые есть в магазине
Его задача оптимально уместить эти вещи в рюкзаке так что бы он унес драгоценностей на максимальную стоимость.
Есть несколько способов решения. Один из них это перебор всех вариантов.
Для простоты, предмета будет только три, поскольку количество различных комбинаций в которых их можно унести растет очень быстро и даже для 3 предметов уже будет равно 8. Оно вычисляется по формуле 2 n где n - количество предметов, то есть если предмета будет 4, то количество возможных комбинаций достигнет уже 16 и так далее. Такой вариант нас не устроит поскольку решая эту задачу онлайн на каком-нибудь Codility ваше решение зарубят с Timeout Exceeded. Нужно что-то получше.
Мы будем решать эту задачу методом динамического программирования
Задача является одной из базовых в этой области и понимание её решения откроет вам дорогу к более сложным задачам. В динамическом программировании мы разбиваем базовую задачу на более простые и постепенно решая их все, в итоге находим решение основной.
Следующая загадка
Два ремня висят на мне,
Есть карманы на спине.
Коль в поход идёшь со мной,
Я повисну за спиной.
Ответ
Рюкзак
Он с тобою и со мною
Шёл лесными стёжками —
Друг походный за спиною
На ремнях с застёжками.
Ответ
Рюкзак
Он заменит десять рук,
Путешественника друг
К пикникам уже привык
И хранит в себе тайник.
Ответ
Рюкзак
Летом я поставлен в угол,
Не наказан, не напуган…
Осенью возьмут меня
Встретить первое сентября.За спиной мой друг сидит,
Книжки, ручки сторожит,
Держится на двух плечах,
Собирают при свечах.
Спрячу книжки под замок
И скорее на урок.
Может влезет и башмак?
В мой вместительный…
Ответ
Рюкзак
Не сундук, но заперт на замок.
В нём не золото, но тоже ценный клад.
Ты берешь его с собою на урок.
Вещи разные обычно в нем лежат…
Ответ
Рюкзак
Взгромоздив его на спину,
Кепку на уши надвину,
Можно ехать на прогулку
По безлюдным переулкам,
Или же с друзьями в лес
Он уже на плечи влез.
Ответ
Рюкзак
Он удобнее, чем сумка,
Лямок две, а не одна.
А у школьника Наума
Выпрямляется спина.
Места в нём, как в трюме много,
Можешь взять с собой в дорогу.
Ответ
Рюкзак
Он не болен, но почему
На спине его несу?
В нём учебники и краски,
Интереснейшие сказки,
Ну а если умудриться,
Может форма поместиться.
Ответ
Рюкзак
Осенью в нём книжки носят,
Зимой с горы катаются.
Но иногда случается,
Что в драке им сражаются.
Следующая загадка
2 взвешивания. Нужно разделить все шары на три части: по 3 шара в двух частях и 2 шара в третьей части. Сначала взвешиваете первые две части по 3 шара. Если одна из частей оказалась тяжелее, то взвешиваем между собой любые 2 шара из нее. Или один из них будет искомым шаром, или не взвешенный, если они оказались равны. В случае равного веса частей при первом взвешивании более тяжелый шар окажется в третьей части из двух шаров.
Мертвец в пустыне
Среди пустыни найден мертвый человек со спичкой в руках, следов нет. От чего он умер и при каких обстоятельствах?
Ответ на загадку про мертвеца в пустыне
Этот вопрос проверяет, насколько хорошо вы умеете восстанавливать события и сопоставлять факты. Человек умер от падения с самолета, который начал терять высоту, и авария была неизбежна. На всех пассажиров не хватило одного парашюта, и они тянули жребий. Ему досталась короткая спичка, и он был вынужден прыгать без парашюта.
4 литра воды
Отмерьте ровно 4 литра, если у вас есть 3-литровая банка, 5-литровая банка и неограниченный доступ к воде.
Ответ на загадку про 4 литра воды
Наберите 5-литровую банку воды и наполните водой из этой банки 3-литровую банку, затем 3-литровую банку вылейте. Два оставшихся литра из 5-литровой банки перелейте в 3-литровую банку. Опять наберите полную 5-литровую банку воды и из нее долейте воды (1 литр) в 3-литровую банку.
Таким образом, в 5-литровой банке останутся 4 литра.
Медведь
Вы построили дом, у которого все стороны смотрят на юг. Вдруг вы увидели медведя. Какого он цвета?
Ответ на загадку про медведя
Белый. Только на Северном полюсе все четыре стены могут быть обращены на юг.
Таблетки
Доктор выдал пациенту 4 таблетки — по 2 таблетки разного вида, которые нельзя отличить по внешним признакам. Таблетки надо выпить за 2 приема: утром по 1 таблетке каждого вида и так же вечером. Если нарушить дозировку или не принять таблетки, пациент умрет. Так вышло, что таблетки перемешались. Как пройти курс лечения и выжить?
Ответ на загадку про таблетки
Конечно, можно сказать, что лучше пойти к врачу и попросить еще, все-таки вопрос жизни и смерти. Но это могут быть единственные таблетки на земле, доктор может исчезнуть при загадочных обстоятельствах и т.д. Так что ответить все же придется. А решение таково: нужно разделить каждую таблетку на 2 части и выпить по половинке каждой из четырех таблеток утром и вечером.
Следующая загадка
Одна женщина жила в двенадцатикомнатной квартире. В каждой комнате у нее висели часы. Одним субботним вечером в конце октября она перевела все часы на зимнее время и легла спать. Проснувшись следующим утром, она обнаружила, что только два циферблата показывают правильное время. Объясните.
Ответ (Десять из двенадцати часов были электронными. Ночью был скачок напряжения и часы сбились. И только двое часов были механическими, поэтому они и показывали правильное время на следующее утро)В некой стране есть два города. В одном из них живут только люди, которые всегда говорят правду, в другом – только те, кто всегда лгут. Все они ходят друг к другу в гости, то есть в любом из этих двух городов можно встретить как честного человека, так и лжеца.
Предположим, вы оказались в одном из этих городов. Как, задав один-единственный вопрос первому встречному, определить, в какой город вы попали – в город честных или в город лжецов?
По некоторым поступившим в полицию города Сан-Франциско сведениям можно было сделать вывод, что готовится похищение драгоценностей жены миллионера миссис Андерсон. Миссис Андерсон жила в одном из первоклассных отелей. По-видимому, здесь же проживал и замысливший злодеяние преступник. Несколько дней дежурил детектив в номере миссис Андерсон в надежде схватить негодяя, но безрезультатно. Миссис Андерсон уже начала подшучивать над ним, как вдруг произошло следующее. Вечером кто-то постучал в дверь номера. Затем дверь открылась, и в комнату заглянул мужчина. Увидев миссис Андерсон, он извинился, сказав, что ошибся дверью.
– Я был абсолютно уверен, что это моя комната, – смущенно проговорил он. – Ведь все двери так похожи одна на другую.
Тут детектив вышел из засады и арестовал незнакомца. Что смогло убедить детектива в том, что перед ним злоумышленник?
Ответ (Мужчина постучался. Значит, он шел не в свою комнату)Путешественник не спал целые сутки. Наконец он добрался до гостиницы и снял номер.
– Будьте любезны, разбудите меня ровно в семь, – попросил он портье.
– Не волнуйтесь, – успокоил его портье. – Я непременно разбужу вас, только не забудьте позвонить мне, а я мигом приду и постучу вам в дверь.
– Буду вам очень признателен, – поблагодарил его путешественник. – Утром получите вдвое больше, – добавил он, протягивая портье чаевые.
Найдите ошибку в этом рассказе.
Ответ (Чтобы позвонить портье, путешественнику придется сначала проснуться)В Муроме построили небоскреб в 230 этажей. Чем выше этаж – тем больше жильцов. На самом верху (230-й этаж) проживает 230 человек. На первом этаже живет только один. Назовите самую нажимаемую кнопку лифта.
Ответ (Кнопка первого этажа)Восемь братьев-близнецов вырвались на выходные в загородный дом, и каждый нашел себе дело по вкусу. Первый занят сбором яблок, второй отправился на рыбалку, третий топит баню, четвертый играет в шахматы, пятый готовит ужин, шестой весь день смотрит сериалы про ментов на ноутбуке, седьмой открыл в себе художника и рисует окружающие пейзажи. Чем в это время занимается восьмой брат?
Ответ (Играет в шахматы с четвертым братом)Во Франции жил-был литературный работник, который терпеть не мог Эйфелеву башню, в особенности то, как она ужасно выглядит. При этом, проголодавшись, он всегда посещал предприятие общепита, расположенное на первом этаже этого архитектурного символа Парижа. Как объясняется такое поведение?
Ответ (Только в этом ресторанчике, выглянув в окно, он не видел Эйфелеву башню)Очень известный английский писатель Бернард Шоу однажды посетил один ресторан со своим коллегой. Они разговаривали друг с другом и не хотели, чтобы им кто-то мешал. Вот к Шоу подходит дирижер оркестра и спрашивает его: «Что сыграть в вашу честь?»
Шоу не хотел, конечно же, никакой музыки и ответил очень остроумно, он сказал: «Я был бы вам весьма благодарен, если бы вы сыграли…»
Читайте также: