MO
У меня есть задача.
Size: a a a
2020 July 22
MO
Написать функцию, возвращающую количество комбинаций заданного набора весов грузиков для заданного веса
MO
здесь надо найти формулу как можно решить потом составлю алгоритм
S
Обычное дп ведь?
MO
что дп не понял
D
Гугли количество разменов монет
D
Это динамическое программирование
MO
понятно
MO
ктото подсказал это решаеться с помшью бином Ньютона
D
Ну задача у тебя ведь найти количество комбинаций грузов, каждая из которых в сумме даёт заданный вес, правильно?
MO
ага
SM
Maxat Oralbaev
Написать функцию, возвращающую количество комбинаций заданного набора весов грузиков для заданного веса
рюкзак
MO
рюкзак
и далее что это подсказка?
SM
Maxat Oralbaev
и далее что это подсказка?
если не слышали советую познакомиться с данным методом решения задач
SM
обычный дп рюкзак
MO
спасибо всем я уже внекаю я раньше не было в этом зоне надо мат скилл развивать
SM
Maxat Oralbaev
спасибо всем я уже внекаю я раньше не было в этом зоне надо мат скилл развивать
скорее алго скилл
SM
тут простой алгоритм....основаный на динамическом программировании
/¯
Maxat Oralbaev
Написать функцию, возвращающую количество комбинаций заданного набора весов грузиков для заданного веса
Пусть у тебя есть грузики весом w1,...wN количеством k1,...,kN штук (максимум, а если не ограничено, то берёшь бесконечность).
Надо найти количество комбинаций с суммарным весом S.
Строишь производящий полином вида
(1+x^w1)^k1 * (1+x^w2)^k2 * .. * (1+x^wN)^kN
Перемножаешь, идешь коэффициент при x^S
Надо найти количество комбинаций с суммарным весом S.
Строишь производящий полином вида
(1+x^w1)^k1 * (1+x^w2)^k2 * .. * (1+x^wN)^kN
Перемножаешь, идешь коэффициент при x^S
/¯
В простонародье такое тоже назовут "динамикой"