Java. Задача о рюкзаке. Динамическое программирование.

[@evgeniifeygin1030]

Если этот разбор популярной задачки можно назвать понятным , то я искренне рад за тех кто что-то тут понял. Автор канала вроде как неоднократно говорил в предыдущих видео, что не важно, что - Имена переменных должны нести смысл ! Почему в этом видео это правило сошло на нет ? Матрица А ( это матрица чего ? отноешния вес к сумме, вес к весу ...?) , переменная к ? Что она отражает ? s...? Почему мы идем по циклу от 0 до ciunt + 1 and maxWeight + 1 ?...

[@arhitutorials]

Названия переменных взяты из предметной области. Если речь идет о матрицах, то логично именовать их так, как принято именовать матрицы.

[@marrustemovich8434]

В данном примере ошибка. Выводить должно [1, 3] , мы все время шли с (k - 1), а в конце поменяли на просто k. Думаю автор спутал с ответом на сайте, но там индексы не с нуля начинаются, а с единицы, поэтому у них этот ответ правильный. Долго по этой причине не мог понять почему тут так, надеюсь это кому-нибудь поможет)

[@John.Constantine.777]

ты полностью прав. автор ленится проверить результат. ленится объяснять если добавить в main следующие строки, то станет понятным что насчитали с превышением вместимости рюкзака, т.е. 14 при максимальной вместимости 13. System.out.println("weight, index: "); for (int i = 0; i < result.size(); i++) { System.out.print(result.get(i)); if (i < result.size() - 1) System.out.print(" + "); } System.out.println(" weight: "); for (int i = 0; i < result.size(); i++) { System.out.print(weights[result.get(i)]); if (i < result.size() - 1) System.out.print(" + "); } int totalW = 0; for (int i = 0; i < result.size(); i++) { totalW += weights[result.get(i)]; } System.out.print(" = " + totalW); System.out.println(" total price: "); for (int i = 0; i < result.size(); i++) { System.out.print(prices[result.get(i)]); if (i < result.size() - 1) System.out.print(" + "); } int totalP = 0; for (int i = 0; i < result.size(); i++) { totalP += prices[result.get(i)]; } System.out.print(" = " + totalP);

[@МихаилНовиков-р6ч]

Когда я играл в Сталкера, Морровинд или прочие игры, где нужно было таскать шмурдяк, такая задача вставала регулярно, как раз применительно к рюкзаку: что взять в город на продажу, что бросить на объекте. Я делал так: для каждого предмета считал коэффициент: стоимость делить на вес. И в первую очередь брал предметы, у которых этот коэффициент максимален. Думаю, что на больших наборах предметов можно было бы использовать такой подход для получения более-менее приемлемого решения за время O(n).

[@floumaster7346]

Я кстати тоже пытался делать жадным алгоритмом, странно что заходила на 85 из 100

[@yushchenkoalexey]

Офигенно, искал разбор этой задачи, a тут видео! Сергею огромная благодарность, а всех с наступающим новым годом!!!

[@marvinheemeyer7027]

да видос зачётный

[@fallerner]

Шапочка добавляет новогоднего настроения :D Спасибо большое за видео)

[@anjelomanoranjan]

Спасибо, Серега! Ты ТОП!

[@solomon4639]

Спасибо за хорошее объяснение и код)

[@i7bro]

Спасибо, крутой материал

[@tasteofhate5884]

Вижу видос Сергея - сразу ставлю лайк)

[@ascar66]

Спасибо за видео!

[@IvanIvanov-dz9xy]

Лайк не глядя!

[@ОвоаоОвоаово]

Классное видео, спасибо большое))

[@carcustomsod_ua4146]

Крутой канал!!

[@AlexSmile-y2x]

Happy New Year!))

[@ИгорьШпура]

красавчик) просто супер контент

[@Инга-ВикторияКуксова]

А есть какой-нибудь вариант этой задачи с возможностью выбора из нескольких вариантов? Вариант, который я хочу реализовать - например, у меня есть 10 супов, 10 гарниров, 10 вторых, 10 салатов, 10 десертов с определённой калорийностью, и я хочу подобрать все возможные варианты комбинаций обедов без повторов между типами еды на определённое заданное число калорий. Можно перебором, но хочется как-то красиво 😅

[@КонстантинОвсянников-я1ш]

Добрый день! А разве побитовый сдвиг для переменной count в первом варианте решения (полным перебором) должен происходить не от значения 1L? В текущем примере должно получиться 2^5 комбинаций, т.е. 32. А при побитовой сдвиге 2L получим 64. Или тогда значение длины массива для сдвига нужно уменьшить на единицу.

[@ПашаНплей]

Тоже это заметил.

[@misha845]

спасибо за то что ты делаешь

[@proctoleha]

Продолжаю наслаждаться, спасибо. Хоть на джаве и не пишу

[@tiagohenrique3505]

Благодарность

[@mykhayloshevchuk1723]

Спасибо бро

[@sergeivilensky5115]

Пили еще )

[@tpahkj1i0katop4]

Сергей, что Вы думаете по поводу режима угнетения в картохе? Я имею ввиду бои 3-15 или 15-3 по кд. Какой алгоритм они используют?

[@arhitutorials]

Если в терминах данного видео, то у них там жадный алгоритм. Работает быстро, но периодически выдает всякую дичь)

[@ПриманкаТВ-о6ш]

Нейронкой может?

[@alex_kq]

Сделай на с++ пожалуйста

[@marvinheemeyer7027]

кто там сказал что математика не нужна?

[@bdfyjdbdfy6157]

10:20 ржачно когда человек объясняя отличия динамического программирования от обычного подхода сравнивает два подхода динамического программирования - табуляцию и мемоизацию. Чувак, если ты внимательно посмотришь то в твоем примере это два одинаковых подхода, просто в первом случае ты выделяешь простые задачи на старте графа, а во втором в конце.