Отсечение
Урок 11 из 15 курса Основы динамического программирования на Coddy.
Отсечение — это метод, используемый для уменьшения количества вычислений, необходимых алгоритму динамического программирования, путем исключения ненужных вычислений. Это достигается за счет исключения определенных ветвей рекурсивного дерева, которые не приведут к лучшему решению, чем лучшее решение, найденное на данный момент. Отсечение может использоваться как в алгоритмах динамического программирования «сверху вниз», так и «снизу вверх».
Задание
ЭкспертВ этом испытании вам дана матрица целых чисел и целевое значение. Ваша задача — выбрать по одному целому числу из каждой строки матрицы так, чтобы абсолютная разница между целевым значением и суммой выбранных чисел была минимальной. Затем вы должны вернуть значение этой минимальной абсолютной разницы.
Попробуйте сами
def minimize_difference(mat, target):
# Напишите здесь кодВсе уроки раздела Основы динамического программирования
1Введение в динамическое программирование
Что такое динамическое программирование?Почему это важно?Применение в различных областях3Алгоритмы динамического программирования
Наибольшая общая подпоследовательностьЗадача о рюкзакеЗадача о размене монетРасстояние редактирования