Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
eugrita
5 / 6 / 4
Регистрация: 18.11.2009
Сообщений: 557
1

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

15.01.2018, 03:46. Просмотров 317. Ответов 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
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.01.2018, 03:46
Ответы с готовыми решениями:

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

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

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

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

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

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

Цитата Сообщение от eugrita Посмотреть сообщение
Является ли задача о размене суммы задачей динамического программирования?
Да.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.01.2018, 16:28

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

Задача
Вокруг костра одним кругом стоят три индейца (A, B, C) и три бледнолицых (D, E,...

Задача
Файл содержал несжатую стереофоническую музыкальную композицию, оцифрованную с...


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

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

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