Matsunaki
@Matsunaki
Любознательный пользователь :)

Как решить задачу с перебором?

Задача следующая:
"Имеется некоторое фиксированное количество монет номиналами 2,3,5. Необходимо составить алгоритм действий, который гарантированно проверит возможность получения задаваемого числа, суммированием имеющимся в наличии монет."
Думал решить через динамический массив и рекурсию, но пока плохо в этом разбераюсь. Может есть другое решение, попроще
  • Вопрос задан
  • 298 просмотров
Пригласить эксперта
Ответы на вопрос 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, гуглер, экс-олимпиадник.
Самое простое решение для понимания - полный перебор. Тупо 3 цикла - сколько монет с номиналом 2 взяли, сколько монет с номиналом 3 и сколько монет с номиналом 5. Каждый цикл от 0 до <Сколько осталось набрать> / номинал. Потом проверяем, что сумма сошлась. Более того, можно последний цикл пропустить и просто проверить, что оставшееся можно набрать пятаками.

bool CanExchange(int n, int have2, int have3, int have5) {
  for(int take2 = 0; take2 <= min(have2, n/2); ++take2) {
    int left2 = n - 2*take2;
    for (int take3 = 0; take3 < min(have3, left2/3); ++take3) {
      int left23 = left2 - take3*3;
      if (left23 % 5 == 0 && left23 / 5 <= have5) {
        return true;
      }
    }
  }
  return false;
}


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

Самое быстрое решение - динамическое программирование.

F(n,k) - можно ли набрать число n первыми k типами монет.

F(0.0) = 1
F(*, 0) = 0
F(n,k) = Sum(i = 0..have[k]) F(n-i*value[k], k-1)

Фактически, это тот же рекурсивный перебор, только с мемоизацией. Можно переписать это двумя циклами и соптимизировать по памяти до O(n).
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы