如何优化递归树遍历？

Question

我最近和一位同事讨论了以下（非常基本的）问题，想知道如何优化它以及优化后的版本会有多长的运行时间。

问题：

你必须 return 一定数量的钱和一套可用的硬币。您可以使用无限数量的硬币。如果不可能 return 这个数额，你应该 return 一个错误。

示例 1：

一套硬币（本例中为欧元，单位为克拉）{200, 100, 50, 20, 10, 5, 2, 1}，总计 return 99.

答案：50, 20, 20, 5, 2, 2

例二：

一套硬币 {50, 20, 2}，总计 return 99.

答案：no solution found!（很明显，因为没有办法return是奇数！）。

我的解决方案：

（代码在此 post 末尾）。我的解决方案是一个递归函数，它是贪婪的，但如果贪婪方法不起作用，则会尝试使用较小的硬币。最后，我基本上是以深度优先的方式遍历解决方案space（一棵树）。

在最坏的情况下（例如{97, 98, 99}和300）找不到解决方案，我必须遍历整棵树，结果是O(l^(a\s))，其中l 是一组硬币的长度（在 EUR 的情况下为 8，在这种情况下为 3），a 是数量（在示例中为 300），s 是可用的最小硬币（97在这个例子中）和 \ 是 integer division。 如有错误请指正.

我正在寻找的优化：

可以看到"solution tree"中有些路径是不需要探索的。这是因为硬币的顺序无关紧要，但仍然遍历了不同的顺序（例如 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

这是一个经典的动态规划问题。可以用O(等于return * 币种数).

来解决

// 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 {};
  }
};

双重可选很有趣。

Live example.

Answer 2

I was thinking about some kind of caching

你描述的问题很经典dynamic programming problem. You simply add a global map to your solution and make your descent a breadth first。一种方法是使用 "frontier list" 一堆硬币的列表（或向量）。您将从 1 堆硬币（值为 0 的空列表）开始。您还将其添加到您的地图中。现在你定义了一个有两个循环的函数。第一个循环遍历边界列表的每个成员，并创建一个新列表。在循环结束时，将新边界列表复制到旧边界列表上并重复。
内循环将每种类型的硬币添加到硬币堆中。然后它会计算硬币的价值，并检查地图以查看该值是否已被计算。如果有那么现有的地图条目必须使用更少的硬币，所以跳过这一新堆。
如果没有，则您已经创建了一个新值，因此将新的堆添加到您的地图以及新的边界列表中。所以在伪代码中。

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;
}

这段伪代码包含了很多优化机会，特别是包含了很多复制。但是，从概念上讲，这就是您使用缓存来避免回溯相同路径的方式。

如何优化递归树遍历？

How to optimize a recursive tree traversal?

c++

tree

recursion

runtime