1
Этот вопрос специально адресован проблеме изменения монет. Я знаю алгоритм, чтобы найти оптимальное количество монет, используемых для поиска изменений для любой суммы, и я также понимаю это, но я не понимаю, как я могу «отметить», если вы пройдете путь к поиску такого решения. Я попытался использовать указатели родителей, которые, я уверен, это способ сделать это, но я просто не знаю, как бы это реализовать. Вот пример. Пример: данные монеты номиналов: 1, 10, 25 Изменение: 30 Оптимальное решение требует: 3 монеты Монеты, используемые: 10, 10, 10Какова хорошая методика вывода решения с использованием динамического программирования?
Я на самом деле не так хорош в решении динамических задач программирования.
Предположим, вы знаете, оптимальное решение с 1 по 29. Как вы могли бы использовать его, чтобы найти решение для 30? – ElKamina
Извините, я забыл сообщить вам, что мое текущее решение проблемы хранится только в массиве, я не делаю таблицу. Поэтому у меня есть решение от 1 -29, но от количества используемых монет, а не от монет. Простите, если это должно быть интуитивно, но это действительно не для меня. Я предполагаю, что мой вопрос: если бы я должен был реализовать таблицу 2d с суммами от 0 до n в виде строк и монетных достоинств от 1 до k в качестве столбцов, каковы были бы значения каждой ячейки и как я мог бы их вычислить? – Sektrax
Вы можете решить эту проблему более эффективно. Держите указатель на предыдущее оптимальное решение, из которого выводится текущее оптимальное решение. Например. Для 10 есть ссылка на ноль. Для 20 ссылок на 10 и для 30 ссылок на 20. Теперь все, что вам нужно сделать, это вернуться. 30 - это 20, так что это 30-20 = 10, 20 - это 10-> 20-10 = 10 и 10-0 = 10. Вот как вы получаете 3 10 – ElKamina