В качестве домашнего задания наш профессор представил нам упрощенную версию задачи по обмену монет, в которой нам не нужно минимизировать количество используемых монет или отслеживать количество возможных комбинаций.Вместо этого нам нужно только определить, равняется ли определенное количество монет одинакового или разного достоинства некоторому количеству M.
Мое уравнение рекурсии задачи выглядит следующим образом:
let k = 0
If ∑ (v1 + v2 + … + vn) = M
return true
If ∑ (v1 + v2 + … + vn) < M
return false
Else
Increment k by 1
make recursive call on coin subset {v1, v2, … v(n-k)}
Следующий вопрос - преобразовать это в псевдокод, который представляет собой динамическое программирование для решения этой проблемы.
Я немного застрял.Если бы вы составляли таблицу из всех возможных сумм {v1 + v2}, {v1 + v2 + v3}, {v1 + v2 + v3 + v4} и т. Д. В конечном итоге вы могли бы найти решение, но это не было быгораздо менее эффективный подход грубой силы?
Я предполагаю, что решение будет включать в себя некоторую реализацию запоминания или какой-либо способ хранения и извлечения уже встречающихся сумм, но, поскольку эта проблема не является проблемой оптимизации, мне трудно представить динамическое решение.
Многие примеры динамического программирования, которые я вижу, предлагают итеративно вычитать элементы, по одному элементу за раз, что похоже на композицию моего уравнения рекурсии, но я не вижу модификации, которая сделала бы этот псевдокоддинамичный по своей природе.
Если бы кто-нибудь мог, пожалуйста, просветить меня, я был бы очень благодарен