297
правок
Изменения
Нет описания правки
3. Метод динамического программирование. Сложность - <tex>O(k \times W)</tex>. Рассмотрим этот алгоритм подробнее.
'''Алгоритм <tex>O(k \times W)</tex>'''
Пусть <tex>A(s, n)</tex> есть максимальная стоимости предметов, которые можно уложить в рюкзак вместимости n, если можно использовать только первые s предметов из заданных k.
Сначала генерируем <tex>А</tex>
for (i = 0; i <= W; ++i):
A[0][i] = 0
for (i = 0; i <= k; ++i):
A[i][0] = 0 {Первые элементы приравниваем 0}
for (s = 1; s <= k; ++s): for (n = 0; n <= W; ++n): {Перебираем для каждого s, все n}
if n >= w[s] {Если текущий предмет можно положить в рюкзак}
Затем найдем набор <tex>ans</tex> предметов, входящих в рюкзак, рекурсивной функцией:
void findAns(int s, int n)
if A[s][n] == 0
if A[s-1][n] == A[s][n]
== Пример ==
