Для студентов по предмету ИнформатикаДинамическое программированиеДинамическое программирование
2023-03-092023-03-09СтудИзба
Задача 2: Динамическое программирование
Описание
Динамическое программирование − 2
1 A. 0-1 рюкзак: точный вес
Разбор:
В этой задаче нужно было определить, можно ли из данных слитков с весами w1, w2, ..., wn набрать вес в точности W, где W - максимальный вес рюкзака.
Будем считать, что:
• Параметры динамики: i - количество уже рассмотренных элементов, j - уже набранный вес
• Состоянием динамики в этой задаче является истинность утверждения "можем ли мы набрать вес j, рассмотрев не более i предметов"
• Переход динамики: мы можем либо набрать этот вес, не используя i-й предмет, в это случае мы переходим из состояния dpi−1,j . Либо мы
можем набрать этот вес, используя его, в этом случае переходим из состояния dpi−1,j−wi .
• База динамики: dp0,0 = T rue, так как мы можем набрать массу 0, не рассмотрев при этом ни одного предмета.
• Обход выполняется сверху вниз, слева направо. Ответ лежит в элементе dpn,w.
Асимптотика решения: O(N × W)
Решение
n , w = map(int , input () . split () )
m = list ( map (int , input () . split () ) )
dp = [[0 for _ in range (w + 1) ] for _ in range (n + 1) ]
dp [0][0] = True
for i in range (1 , n + 1) :
for j in range ( w + 1) :
dp [i ][ j] = dp [i - 1][ j] or (j - m[ i - 1] >= 0 and dp [i -
1][ j - m [i - 1]])
print (’yes ’ if dp [n ][ w] else ’no ’) Показать/скрыть дополнительное описание
1 A. 0-1 рюкзак: точный вес
Разбор:
В этой задаче нужно было определить, можно ли из данных слитков с весами w1, w2, ..., wn набрать вес в точности W, где W - максимальный вес рюкзака.
Будем считать, что:
• Параметры динамики: i - количество уже рассмотренных элементов, j - уже набранный вес
• Состоянием динамики в этой задаче является истинность утверждения "можем ли мы набрать вес j, рассмотрев не более i предметов"
• Переход динамики: мы можем либо набрать этот вес, не используя i-й предмет, в это случае мы переходим из состояния dpi−1,j . Либо мы
можем набрать этот вес, используя его, в этом случае переходим из состояния dpi−1,j−wi .
• База динамики: dp0,0 = T rue, так как мы можем набрать массу 0, не рассмотрев при этом ни одного предмета.
• Обход выполняется сверху вниз, слева направо. Ответ лежит в элементе dpn,w.
Асимптотика решения: O(N × W)
Решение
n , w = map(int , input () . split () )
m = list ( map (int , input () . split () ) )
dp = [[0 for _ in range (w + 1) ] for _ in range (n + 1) ]
dp [0][0] = True
for i in range (1 , n + 1) :
for j in range ( w + 1) :
dp [i ][ j] = dp [i - 1][ j] or (j - m[ i - 1] >= 0 and dp [i -
1][ j - m [i - 1]])
print (’yes ’ if dp [n ][ w] else ’no ’) Показать/скрыть дополнительное описание
Динамическое программирование 2. Методы и способы написания процедурного программирования. Динамика и аналитика данных..
Характеристики решённой задачи
Предмет
Учебное заведение
Неизвестно
Семестр
Номер задания
Просмотров
1
Покупок
0
Качество
Идеальное компьютерное
Размер
207,37 Kb
Список файлов
- Динамическое программирование 2.pdf 207,37 Kb
QuadD4rv1n7
QuadD4rv1n7
09 марта в 22:11
