5 / 6 / 4
Регистрация: 18.11.2009
Сообщений: 661
1

Задача о размене -задача динамического программирования?

15.01.2018, 03:46. Показов 1770. Ответов 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

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
15.01.2018, 03:46
Ответы с готовыми решениями:

Задача о точках и отрезках. Метод динамического программирования
Добрый вечер, помогите пожалуйста разработать алгоритм для решения задачи: На прямой задано N...

Задача линейного программирования
Помогите решить задачу.

Задача Дам или задача Восьми
помогите найти ошибку в алгоритме. не находит ответ подозреваю ошибку в k, i, j package...

Алгоритм решения задач динамического программирования
Здравствуйте, нужно решить следующую задачу посредством метода динамического программирования....

1
Модератор
2819 / 1979 / 429
Регистрация: 26.03.2015
Сообщений: 7,557
15.01.2018, 16:28 2
Цитата Сообщение от eugrita Посмотреть сообщение
f(30)=f(23)+f(27)+f(25)
Что это значит?

Цитата Сообщение от eugrita Посмотреть сообщение
Является ли задача о размене суммы задачей динамического программирования?
Да.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
15.01.2018, 16:28

Метод динамического программирования для задачи поиска наибольшей чередующейся подпоследовательности
Задача о поиске наибольшей чередующейся подпоследовательности. Имеется последовательность....

Задача методом динамического программирования
Добрый день. Передо мной стоит решение задачи методом динамического программирования (табличный...

Задача о рюкзаке методом динамического программирования
Здравствуйте, помогите, пожалуйста, реализовать до конца программу. Входные данные должны быть...

Задача коммивояжера методом динамического программирования
Помогите пожалуйста переделать коммивояжера методом динамического программирования. Пусть n - это...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.