5 / 6 / 4
Регистрация: 18.11.2009
Сообщений: 661
|
|
1 | |
Задача о размене -задача динамического программирования?15.01.2018, 03:46. Показов 2068. Ответов 1
Метки нет Все метки)
(
Является ли задача о размене суммы задачей динамического программирования?
Мне кажется нет. хотя это зависит от алгоритма решения. Здесь обычно путают 2 задачи 1)задача нахождения количеств способов размена с учетом порядка купюр одинакового достоинства да ,в этом случае алгоритм заключается в нахождении количества путей между начальной вершиной и нулевыми или например в написании рекурсивных формул сведения к меньшей размерности например S=30 f(30)=f(23)+f(27)+f(25) f(0)=1 f(23)=f(16)+f(20)+f(18) f(27)=f(20)+f(24)+f(22) f(25)=f(18)+f(22)+f(20) и т д пока не доходят до 0 а потом обратно вверх 2)задача нахождения количества способов размена без учета порядка купюр одинакового достоинства - здесь уже проходы по дереву не ведет к решению - надо считать одинаковыми все пути с одинаковым кол-вом купюр одних достоинств. (или делить на количество перестановок) Я сам решаю данную задачу алгоритмом лексикографического перебора по комбинациям монет начиная от мах количества самых крупных купюр в сторону уменьшения. Это можно назвать задачей целочисленной оптимизации но никак по-моему динамическим программированием. Нет там ни рекурсивного обхода дерева, ни приема "c конца" Правда для этой задачи в литературе иногда используют термин жадный алгоритм. Но я не виде подробного его описания
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
|
|
15.01.2018, 03:46 | |
Ответы с готовыми решениями:
1
Задача линейного программирования Задача Дам или задача Восьми
|
Модератор
2968 / 2107 / 450
Регистрация: 26.03.2015
Сообщений: 8,227
|
|
15.01.2018, 16:28 | 2 |
0
|
15.01.2018, 16:28 | |
Помогаю со студенческими работами здесь
2
Метод динамического программирования для задачи поиска наибольшей чередующейся подпоследовательности Задача методом динамического программирования
Задача коммивояжера методом динамического программирования Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |