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

Question

[Кирилл Инкогнатович]

Задача следующая:
"Имеется некоторое фиксированное количество монет номиналами 2,3,5. Необходимо составить алгоритм действий, который гарантированно проверит возможность получения задаваемого числа, суммированием имеющимся в наличии монет."
Думал решить через динамический массив и рекурсию, но пока плохо в этом разбераюсь. Может есть другое решение, попроще

Comments

[Кирилл Инкогнатович]

Можно сделать на любом языке, удобном для вас :)

[dollar]

Сделать-то можно. Делайте.
В чем проблема-то у вас? Разобраться в устройстве массивов и рекурсии?
P.S. Задачки здесь запрещены.

Answer 1

[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).