MO
самый классыный ответ спасибо админ ))))
Size: a a a
2020 July 22
/¯
Ток без анимированных стикеров, флудилка в соседнем чате(
MO
окау
SM
Пусть у тебя есть грузики весом 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
можете посоветовать какую нибудь книгу или статью для того чтобы лучше разбираться во всем этом с математической точки зрения?
MO
я нашел простой сайт про мат
SM
Пусть у тебя есть грузики весом 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
или поподробнее объяснить это решение
SM
Maxat Oralbaev
я нашел простой сайт про мат
какой?
MO
MO
так ясно и с примерами обьяснают
/¯
можете посоветовать какую нибудь книгу или статью для того чтобы лучше разбираться во всем этом с математической точки зрения?
Не могу сходу что-то посоветовать из литературы, но можно искать по тегам "производящие полиномы", "теорема Пойа" и "лемма Бёрнсайда", они все очень связаны
SM
Maxat Oralbaev
спасибо всем я уже внекаю я раньше не было в этом зоне надо мат скилл развивать
метод динамики таков
пусть мы знаем ответ для i - 1 камней. количество способов представить вес j (0 <= j <= нужныйвес) и скажем для i - 1 первых элементов и веса j сохраняем ответ в d(i - 1, j)
как составить ответ для i первых камней?
пройдемся по всем j (0 <= j <= нужный вес)
d(i , j) = d(i - 1, j) + d (i - 1, j - a[i]) если j >= a[i]
иначе d (i , j) = d (i - 1, j)
и мы составили ответы для всех весов 0 <= j <= n для первых i камней
когда дойдем до n и пересчитаем все то ответ будет храниться в d (количесво камней, нужный вес )
пусть мы знаем ответ для i - 1 камней. количество способов представить вес j (0 <= j <= нужныйвес) и скажем для i - 1 первых элементов и веса j сохраняем ответ в d(i - 1, j)
как составить ответ для i первых камней?
пройдемся по всем j (0 <= j <= нужный вес)
d(i , j) = d(i - 1, j) + d (i - 1, j - a[i]) если j >= a[i]
иначе d (i , j) = d (i - 1, j)
и мы составили ответы для всех весов 0 <= j <= n для первых i камней
когда дойдем до n и пересчитаем все то ответ будет храниться в d (количесво камней, нужный вес )
SM
метод динамики таков
пусть мы знаем ответ для i - 1 камней. количество способов представить вес j (0 <= j <= нужныйвес) и скажем для i - 1 первых элементов и веса j сохраняем ответ в d(i - 1, j)
как составить ответ для i первых камней?
пройдемся по всем j (0 <= j <= нужный вес)
d(i , j) = d(i - 1, j) + d (i - 1, j - a[i]) если j >= a[i]
иначе d (i , j) = d (i - 1, j)
и мы составили ответы для всех весов 0 <= j <= n для первых i камней
когда дойдем до n и пересчитаем все то ответ будет храниться в d (количесво камней, нужный вес )
пусть мы знаем ответ для i - 1 камней. количество способов представить вес j (0 <= j <= нужныйвес) и скажем для i - 1 первых элементов и веса j сохраняем ответ в d(i - 1, j)
как составить ответ для i первых камней?
пройдемся по всем j (0 <= j <= нужный вес)
d(i , j) = d(i - 1, j) + d (i - 1, j - a[i]) если j >= a[i]
иначе d (i , j) = d (i - 1, j)
и мы составили ответы для всех весов 0 <= j <= n для первых i камней
когда дойдем до n и пересчитаем все то ответ будет храниться в d (количесво камней, нужный вес )
а если постараться то можно уменьшить алгоритм по памяти так как нам необходим лишь i - 1 элемент то достаточно хранить веса а елементы сами не нужны...
SM
с двумерной спустились до одномерной динамики
MO
метод динамики таков
пусть мы знаем ответ для i - 1 камней. количество способов представить вес j (0 <= j <= нужныйвес) и скажем для i - 1 первых элементов и веса j сохраняем ответ в d(i - 1, j)
как составить ответ для i первых камней?
пройдемся по всем j (0 <= j <= нужный вес)
d(i , j) = d(i - 1, j) + d (i - 1, j - a[i]) если j >= a[i]
иначе d (i , j) = d (i - 1, j)
и мы составили ответы для всех весов 0 <= j <= n для первых i камней
когда дойдем до n и пересчитаем все то ответ будет храниться в d (количесво камней, нужный вес )
пусть мы знаем ответ для i - 1 камней. количество способов представить вес j (0 <= j <= нужныйвес) и скажем для i - 1 первых элементов и веса j сохраняем ответ в d(i - 1, j)
как составить ответ для i первых камней?
пройдемся по всем j (0 <= j <= нужный вес)
d(i , j) = d(i - 1, j) + d (i - 1, j - a[i]) если j >= a[i]
иначе d (i , j) = d (i - 1, j)
и мы составили ответы для всех весов 0 <= j <= n для первых i камней
когда дойдем до n и пересчитаем все то ответ будет храниться в d (количесво камней, нужный вес )
спасибо за ответ буду учитовать это тоже )))
2020 July 23
/¯
2020 July 24
Д🍋
Ш
Если есть n <= 12 точек на плоскости где координаты точек по модулю <= 1e4, как найти сколько минимум прямых нужно чтобы любую пару точек отделяла какая то прямая
Ш
Ш
Кто то знает как решить ?
EZ
Кто то знает как решить ?
Для каждого подмножества проверять отделяется ли оно от всего остального?