Как оптимизировать рекурсивный обход дерева?

Question

Я недавно обсуждал с коллегой следующую (вполне базовую c) проблему и хотел бы знать, как ее оптимизировать и во время выполнения оптимизированной версии.

Проблема:

Вы должны вернуть сумму денег с доступным набором монет. У вас есть неограниченное количество монет. Если невозможно вернуть эту сумму, вы должны вернуть ошибку.

Пример 1:

Набор монет (в данном случае евро, в кт) {200, 100, 50, 20, 10, 5, 2, 1}, сумма возврата 99.

Ответ: 50, 20, 20, 5, 2, 2

Пример 2:

Набор монет {50, 20, 2}, сумма возврата 99.

Ответ: no solution found! (очевидно, поскольку невозможно вернуть нечетное число!).

Мое решение:

(код в конце этого поста). Мое решение - это рекурсивная функция, которая жадная, но попытается использовать меньшие монеты, если жадный подход не работает. В конце концов, я в основном пересекаю пространство решений (дерево) в глубину.

В худшем случае (например, {97, 98, 99} и 300) решение не найдено, и я должен пройти по всему дереву, что приводит к O(l^(a\s)), где l - длина набора монет (8 в случае EUR, 3 в этом случае), a - сумма (300 в примерах) s - наименьшая из доступных монет (в данном примере 97), а \ - целочисленное деление . Пожалуйста, исправьте меня, если я ошибаюсь .

Оптимизация, которую я ищу:

Вы видите, что есть некоторые пути в " дерево решений ", которые не нужны для изучения. Это связано с тем, что порядок монет не имеет значения, но различные порядки все еще проходят (например, 99, 98, 97 и 98, 99, 97 - оба). Как я могу обрезать дерево таким образом, чтобы обходились только необходимые пути? Я думал о каком-то кешировании, но не могу придумать что-нибудь умное. Какой будет среда выполнения такого решения?

C ++ 17 Код:

#include <iostream>
#include <list>
#include <optional>
#include <string>

std::string print_list(std::optional<std::list<int>> lst)
{
    if (lst)
    {
        std::string res = "";
        for (int num : lst.value())
        {
            res += std::to_string(num) + ", ";
        }
        return res + "\n";
    }
    return "no solution found!\n";
}

std::optional<std::list<int>> get_coins(int remainder, std::list<int> &currency, std::list<int> coins)
{
    if (remainder == 0)
    {
        return std::optional{coins};
    }
    for (int coin : currency)
    {
        if (coin <= remainder)
        {
            coins.push_back(coin);
            auto result = get_coins(remainder - coin, currency, coins);
            if (result)
            {
                return result;
            }
        }
    }
    return std::nullopt;
}

int main()
{
    // Example 1
    std::list<int> eur{200, 100, 50, 20, 10, 5, 2, 1};
    std::cout << print_list(get_coins(99, eur, {})); // 50, 20, 20, 5, 2, 2,
    // Example 2
    std::list<int> fail{50, 20, 2};
    std::cout << print_list(get_coins(99, fail, {})); // no solution found!
}

Answer 1

Это классическая c Dynami c проблема программирования. Его можно решить в O (сумма для возврата * количество типов монет).

// named vector.  A vector of coin values.
struct currency {
  std::vector<int> values;
  int const* begin() const {return values.data();}
  int const* end() const {return values.data()+values.size();}
};
// named map.  A map of coin counts
struct coins {
  std::map<int, int> count;
  // helper to remove bounds-checking elsewhere
  void add_coin( int type ) {
      ++count[type];
  }
};
struct coins_required {
  std::vector<std::optional<std::optional<int>>> count = {{0}}; // number of coins required for [i] money
  // outer optional is "have I solved this", inner is "is this possible".

  // save on bounds checking code elsewhere.
  // note, is only trustworthy if someone called solve on i already.
  std::optional<std::optional<int>> operator[](int i) {
    if (count.size() <= i) count.resize(i+1);
    return count[i];
  }
  // finds the number of coins required to make up "i" money
  std::optional<int> solve( int i, currency const& c ) {
    //std::cerr << "Solving for " << i << "\n";
    if (i == 0)
    {
      return 0;
    }
    if ( (*this)[i] )
    {
      //std::cerr << "Answer is: ";
      if (*(*this)[i]) {
        //std::cerr << **(*this)[i] << "\n";
      } else {
        //std::cerr << "no solution\n";
      }
      return *(*this)[i];
    }
    std::optional<int> solution = {};
    for (auto coin:c) {
      if (i < coin) continue;
      std::optional<int> subsolution = solve( i-coin, c );
      if (!subsolution)
        continue;
      if (solution) {
        *solution = (std::min)( *subsolution + 1, *solution );
      } else {
        solution = *subsolution + 1;
      }
    }
    // count[] is safe, as we used *this[] above
    count[i] = solution;
    if (solution)
    {
      //std::cerr << i << " needs " << *solution << " coins\n";
    }
    return solution;
  }
  // returns a vector of coin counts for money value i, given currency c.
  std::optional<coins> get_coins( int i, currency const& c ) {
    if (i==0) return coins{};
    auto count = solve(i, c);
    if (!count) return {}; // no solution
    for (auto coin:c) {
      // can we remove this coin?
      if (coin > i)
        continue;
      // Does removing this coin result in an optimal solution?
      auto subsolution = solve(i-coin, c);
      if (!subsolution || *subsolution +1 > *count)
        continue;
      // recurse!  If we hit this, we should be guaranteed a solution.
      auto retval = get_coins( i-coin, c );
      assert(retval); // logically impossible
      if (!retval) continue;
      retval->add_coin(coin);
      return retval;
    }
    assert(false);// logically impossible to reach
    return {};
  }
};

Двойной необязательный забавный.

Живой пример .

Answer 2

Я думал о каком-то типе кэширования

Проблема, которую вы описываете, - это проблема classi c dynamici c программирования . Вы просто добавляете глобальную карту в свое решение и делаете спуск шириной вначале . Один из способов сделать это - создать «пограничный список» - список (или вектор) куч монет. Вы начнете с 1 стопки монет (пустой список со значением 0). Вы также добавляете это на свою карту. Теперь вы определяете функцию, которая имеет два цикла. Первый l oop проходит через каждого члена вашего пограничного списка и составляет новый список. В конце l oop скопируйте новый пограничный список поверх старого и повторите.
Внутренний l oop добавляет монету каждого типа в стопку монет. Затем он вычисляет стоимость монет и проверяет карту, чтобы увидеть, было ли это значение уже сделано. Если у него есть, то существующая запись карты должна использовать меньше монет, поэтому пропустите эту новую стопку.
Если нет, вы создали новое значение, поэтому добавьте новую стопку на карту, а также в новый список границ , Таким образом, в псевдокоде.

frontier_list.push_back(Pile{});
while(!map.contains[target_value]) {
    for (const auto& pile: frontier_list)
        for (const auto& coin: coin_list) {
            const auto new_pile = pile + coin;
            const auto value = add_coins(new_pile);
            if (!map.contains(value)) {
                new_frontier_list.push_back(new_pile);
                map[value] = new_pile;
            }
       }
   }
   frontier_list = new_frontier_list;
}

Этот псевдокод содержит множество возможностей оптимизации, в частности, большое количество копий. Однако, концептуально, именно так вы используете кеширование, чтобы избежать повторного прохождения тех же путей.