ACMP 646: различия между версиями
Перейти к навигации
Перейти к поиску
Ctrlalt (обсуждение | вклад) Нет описания правки |
Ctrlalt (обсуждение | вклад) Нет описания правки |
||
| Строка 14: | Строка 14: | ||
[[Category: Сборник задач: ACMP]] | [[Category: Сборник задач: ACMP]] | ||
[[Category: Задачи: Динамическое программирование — префикс, параметр]] | [[Category: Задачи: Динамическое программирование — префикс, параметр]] | ||
[[Category: Задачи: Рюкзак]] | |||
Текущая версия от 11:08, 19 апреля 2015
Ссылка на задачу
Комментарии
Вид подзадачи: d[i][j] — количество способов набрать i конфет, используя коробки 0..j.
Рекуррентная формула: d[i][j] = d[i][j - 1] + d[i - w[j]][j - 1].
База рекурсии: d[0][0] = 1.
Вид ответа: max(0, 2n - 2 × ∑d[i][n]), где i ∈ 0..(k - 1). Сложность O(N2).