Содержание
- 2. Динамическое программирование – метод проектирования алгоритмов. Предложен американским математиком Ричардом Беллманом как общий метод оптимизации многостадийных
- 3. Иллюстрация метода на примере чисел Фибоначчи 0, 1, 1, 2, 3, 5, 8, 13… F(n)=F(n-1) +
- 4. 5.1. Вычисление биномиальных коэффициентов Биномиальным коэффициентом С(n, k) называется количество комбинаций (подмножеств) из k элементов из
- 5. Таблица для вычислений биномиальных коэффициентов
- 6. Алгоритм Binomial (n,k) // Вх. данные: Пара неотрицательных чисел n≥k ≥0 // Вsх. данные: Значение C(n,k)
- 7. Оценка эффективности алгоритма вычисления биномиальных коэффициентов Базовая операция – сложение. A(n,k) – общее количество сложений при
- 8. 5.2. Задача о рюкзаке и функции с запоминанием Дано: Рюкзак вместимостью W Количество предметов: n Веса
- 9. Экземпляр задачи, определяемый первыми i предметами (1≤i ≤ n) Веса: w1 , w2 , …,wn Стоимости:
- 10. Все подмножества первых i предметов, которые помещаются в рюкзак ёмкостью j делятся на две категории: те,
- 11. Рекуррентное соотношение max{V[i-1,j], vi +V[i-1, j-wi]}, если j-wi≥0 V[i,j]= V[i-1,j], если j-wi Начальные условия: V[0,j]=0 при
- 12. Таблица для решения задачи о рюкзаке методом динамического программирования
- 13. Пример 1. W=5
- 14. Ёмкость j
- 16. Скачать презентацию