Вариация 1:
Что если в задаче о смене монет вам нужно было найти минимальное количество номиналов, которое можно использовать для внесения изменений для входа X. Я понимаю подход Greedy & DP для этого .
- Попробуйте все возможные комбинации размера r (от r = 1 до n) и посмотрите, какая из них работает.
- Создайте матрицу измерений (x + 1) xn и используйте DP.
Я думал о рекурсивном решении, где для каждого номинала d[i] я буду рекурсивно вызывать функцию min_cur, когда исключено d[i] и когда включено хотя бы d[i] и выберите минимум из двух.
for all i range of d[0] to d[n]
min_cur( x -> (d[1], d[2], …, d[n]) ) =
minimum( min_cur( x -> (d[1], d[2], …, d[n] excluding d[i]) ),
min_cur( (x-i) -> (d[1], d[2], …, d[n]) ).
, но эта рекурсия всегда дает ответ как 1.
Требуется некоторое уточнение. Я не уверен, как это уточнить. Кроме того, что, если вы также хотите напечатать все использованные купюры?
Вариация 2:
Та же проблема, что и выше, но с ограниченным количеством монет для каждой купюры - т.е. для d[i], Вы можете максимально использовать l[i] монеты. Имеет ли это оптимальную основу? Я не уверен, так как подзадачи зависят друг от друга. Какой самый лучший жадный подход для этого?