英文:

Find an algorithm for quickly computing results to a given equation

问题

以下是您的翻译请求的结果：

有一个方程式：

280a + 80b + 75c + 50d + 25e - 30f - 42g = R

• a, b, c, d, e, f, g - 这些是修饰符。它们是严格的正整数值。

• R - 这是解决范围，只要方程左边的结果落入该范围内，方程就有效。

目标是：

• 对于变量集的每个可能的子集，找到修饰符值的最小总和，使得方程左边的结果在给定的解决范围内。

子集由修饰符的包含定义。即，修饰符可以是== 0或> 0。
例如：

• b, c, d, e, f, g == 0，a > 0是第一个子集

• a, c, d, e, f, g == 0，b > 0是第二个子集

• c, d, e, f, g == 0，a, b > 0是第三个子集

• 等等...

基本上这就像是二进制计数。因此，总共有128个子集（实际上是127个，因为不需要所有修饰符== 0的子集作为解决方案）。

注意：我知道e可以替代c, d的修饰符，因为它们都可以被e整除，但出于唯一排列的考虑，我仍然需要将它们作为单独的修饰符。

基本上，解决范围是输入，结果应该是一个所有有效子集的修饰符最小总和的列表。

这是一个有效结果的示例：

• 假设我们输入的范围是从-2到-2

以下是一些不同子集（不是所有可能的子集）的最小解决方案列表，只使用b, c, d, e, f, g修饰符：https://imgur.com/a/ZlWeAlq（排列==子集，我当时没有使用正确的术语）。

将这些值代入方程将在每个子集上得到-2的结果（假设a修饰符为0，我没有在我的第一个求解器中包括它）。

我在C#中制作了一个快速的蛮力解决方案，使用了并行循环，只需遍历所有可能的值（在边界内），直到找到所有解决方案，但速度非常慢。

我考虑过的几种算法：

1. 广度优先搜索：

   • 添加每个修饰符的1，并检查是否有任何单独的“节点”是解决方案。然后将每个修饰符的1添加到每个先前的节点中，看看新节点中是否有解决方案。

     1. 我必须设法优化它，以避免多次检查相同的路径，因为以不同的顺序添加2个修饰符将导致相同的节点

     2. 这会在内存方面增长得非常快，因此我必须将其限制在某个值范围内，以允许这种“分支”，然后只允许在该“分支范围”接近解决范围时添加相同的修饰符。类似于：

        • 如果解决范围是500-550之类的东西，我只允许正系数修饰符相互添加，直到每个节点的值在解决范围的100内

2. 简化任意工作答案：

   • 计算您可以创建的最小差值，考虑所选修饰符集合

   • 计算需要将多少最小差值相加才能进入解决范围，这可以使用大量修饰符，但它是一个有效的答案

   • 使用表格快速简化/中和修饰符，直到获得最小可能值

3. 蛮力，但具有更多优化：

   • 我可以在蛮力算法中添加相同的范围检查，以便仅尝试给定范围内的每种组合，同时消除一些不必要的重复（我的当前解决方案非常糟糕）

我能够立即想到的另一个希望不错的优化是，在一开始删除对于给定范围不可能的子集。

例如，如果范围是正数，那么仅具有正系数的f, 仅有正系数的g或仅有正系数的f, g 修饰符的子集永远不会是有效答案，因为这些都有负系数（无法通过添加负值来达到正数范围）。

因此，我的问题的核心是：

• 哪种算法，无论是我考虑过的还是我没有考虑过的现有算法，都能够迅速有效地解决这个问题？
• 这样的算法的基本实现会是什么样子？

我还没有尝试实现其中任何一个，因为我不确定它们是否有效，以及是否有任何现有的算法会比我能想到的任何东西要好得多。我的蛮力解

英文:

There is an equation:

280a + 80b + 75c + 50d + 25e - 30f - 42g = R

• a, b, c, d, e, f, g - those are modifiers. They're strictly positive integer values.

• R - this is a solution range, the equation is valid as long as the result of its left side falls into that range.

---

The goal is:

• For each possible subset of the variable set find the smallest sum of modifiers values such that the result of the left side of the equation is within given solution range.

Subsets are defined by inclusion of modifiers. I.e., modifier can either == 0 or > 0.
For example:

• b, c, d, e, f, g == 0 and a > 0 is 1st subset

• a, c, d, e, f, g == 0 and b > 0 is 2nd subset

• c, d, e, f, g == 0 and a, b > 0 is 3rd subset

• etc...

Basically it's like counting in binary. Ergo there's a total of 128 subsets (technically 127 since a subset where all modifiers == 0 isn't needed as a solution).

Note: I know that e can replace c, d modifiers as both of these are divisible by it, but I still need those as separate modifiers for the sake of unique permutations.

Basically, the solution range is the input and the result should be a list of all valid subsets with the smallest sum of modifiers

Here's an example of a valid result:

• Let the range we input be from -2 to -2

Here's a list of smallest solutions for a couple different subsets (not all possible) with just b, c, d, e, f, g modifiers: https://imgur.com/a/ZlWeAlq (permutation == subset, I didn't use the correct terminology at the time).

Plugging these values in the equation will result in -2 on every subset (assume a modifier is 0, I didn't include it in my first solver).

---

I made a quick bruteforce solution in C# with a parallel loop just going over all possible values (within boundaries) until it finds all solutions, but it's painfully slow.

A couple algorithms I have considered:

1. Breadth-first search:

   • Add 1 of each modifier and check if any individual "node" is a solution. Then add 1 of each modifier to each previous node and see if any of the new nodes are solutions.

     1. I'll have to somehow optimize it to not check the same path multiple times since adding 2 modifiers in different order will lead to the same node

     2. This grows really fast in terms of memory, so I'll have to limit it to some range of values within which I allow this "branching", and then I'll only allow addition of identical modifiers until that "branching range" is close enough to the solution range. Something like:

        • if a solution range is smth like 500-550, I'll only allow modifiers with positive coefficients to be added to itself until the value on each node is within 100 of the solution range

2. Simplify an arbitrary working answer:

   • Calculate the minimum difference you can create given the selected modifier set

   • Calculate how many minimum differences added together it takes to get into a solution range which can give a large number of modifiers being used but its a working answer

   • Use a table to quickly simplify/neutralize the modifiers with each other until you get the minimum possible

3. Bruteforce, but with even more optimization:

   • I could add the same range check to a bruteforce algorithm so that it only tries every combination within a given range, as well as remove some unnecessary repetitions (my current solution sucks quite hard)

Another hopefully decent optimization I can think of right off the bat is to remove impossible subsets for a given range at the very start.

For example, if a range is positive, then subsets where only f, only g or only f, g modifiers are > 0 will never be a valid answer since both of these have negative coefficients (can't ever reach a positive range by adding negative values).

---

So the essence of my question is:

• Which algorithm, either from the ones that I thought of or from other existing algorithms that I didn't think of, would be able to quickly and efficiently solve this problem?
• How would a basic implementation of such algorithm look like?

I have yet to try to implement any of these since I'm not sure whether they will be good at all and if there are any existing algorithms that would be much better than any of the things I could think of. My bruteforce solution still exists and, if needed, I can link it. It is terribly slow tho and definitely not worth comparison in its current form.

答案1

得分: 1

以下是您的翻译：

我的解决方案的主要思路是简单的BFS。对于给定的子集，您从具有关联值（等式左侧的和）和成本（修饰符的和）的初始配置开始，在每个步骤中，从队列中提取最便宜的配置，考虑每个邻居（通过增加单个修饰符相邻）。

一些必要的观察。如果有多个产生相同值的配置，则只需考虑其中一个成本最低的配置，因此每个不同的值最多只会放入队列一次。如果我们在目标范围下方，就不需要添加负修饰符，如果我们在目标范围上方，就不需要添加正修饰符，因此搜索空间受到明显限制。

这提供了一个解决方案，为给定范围 R = [from, to] 和掩码在 O(max(|from|, |to|)) 内存和时间内构建最低成本的配置。请注意，尽管解决任何给定范围，我们将遇到许多其他查询的解决方案，但将它们丢弃是浪费的。

实施示例 #1，C++，从头开始解决每个查询：

#include <array>
#include <iostream>
#include <limits>
#include <numeric>
#include <queue>
#include <vector>

constexpr int N = 7;

// 这对应于问题中截图上的子集排序
constexpr std::array<int, N> coef{-42, 75, -30, 80, 25, 50, 280};

struct Solution {
  int lhs;
  std::array<int, N> mods;
};

Solution solve(int mask, int l, int r) {
  Solution init{};
  int low = std::numeric_limits<int>::max(), high = std::numeric_limits<int>::min();
  for (int i = 0; i < N; ++i) if (mask & 1 << i) {
    init.lhs += coef[i];
    init.mods[i] = 1;
    low = std::min(low, r + 1 + coef[i]);
    high = std::max(high, l - 1 + coef[i]);
  }
  if (l <= init.lhs && init.lhs <= r) {
    return init;
  }
  low = std::min(low, init.lhs);
  high = std::max(high, init.lhs);
  std::queue<int> q;
  q.push(init.lhs - low);
  std::vector<int8_t> last_move(high - low + 1);
  last_move[init.lhs - low] = -1;
  int restore_from = 0;
  l -= low, r -= low;
  while (!q.empty()) {
    int cur_val = q.front();
    q.pop();
    for (int i = 0; i < N; ++i) if (mask & 1 << i) {
      if (coef[i] < 0? cur_val < l: cur_val > r) {
        continue;
      }
      int next_val = cur_val + coef[i];
      if (last_move[next_val]) {
        continue;
      }
      last_move[next_val] = i + 1;
      if (l <= next_val && next_val <= r) {
        restore_from = next_val;
        q = {};
        break;
      }
      q.push(next_val);
    }
  }
  if (l > restore_from || restore_from > r) {
    return {l + low - 1, {}};
  }
  init.lhs = restore_from + low;
  while (last_move[restore_from] != -1) {
    ++init.mods[last_move[restore_from] - 1];
    restore_from -= coef[last_move[restore_from] - 1];
  }
  return init;
}

int main() {
  int64_t sum = 0;
  for (int R = -5000; R <= 5000; ++R) {
    for (int mask = 0; mask < 1 << N; ++mask) if (auto res = solve(mask, R, R); res.lhs == R) {
      sum += std::accumulate(res.mods.begin(), res.mods.end(), 0);
    }
  }
  std::cout << sum << '\n';
}

在 solve 函数内部的注释行是一些微小的优化，如果取消注释，可以提高运行速度大约两倍。这不是这种方法的最优化实现，因为我拥有的稍微更快的另一种版本不太容易阅读，据我所知，不可能转化为C＃。如果去掉这些优化，此代码在我的当前计算机上大约需要6秒，独立解决从-5000到5000的每个单位范围。

实施示例 #2，C++，预计算每个单位范围（from == to）的最低成本：

#include <algorithm>
#include <array>
#include <cassert>
#include <iostream>
#include <limits>
#include <numeric>
#include <queue>
#include <vector>

constexpr int N = 7;

// 这对应于问题中截图上的子集排序
constexpr std::array<int, N> coef{-42, 75, -30, 80, 25, 50, 280};

struct Solution {
  int lhs;
  std::array<int, N> mods;
};

class Precalc {
public:
  Precalc(int min_R, int max_R)
      : min_R{min_R},
        max_R{max_R},
        low_val{std::min({min_R, 0, min_R + 1 + *std::min_element(coef.begin(), coef.end())})},
        high_val{std::max({max_R, 0, max_R - 1 + *std::max_element(coef.begin(), coef.end())})},
        last_move{},
        cost{} {
    for (int mask = 0; mask < 1 << N; ++mask) {
      last_move[mask].resize(high_val - low_val + 1);
      cost[mask].resize(high_val - low_val + 1);
      do_precalc(mask);
    }
  }

  Solution get_solution(int mask, int from, int to) const {
    assert(min_R <= from && from <= to && to <= max_R);
    int best_cost = std::numeric_limits<int>::max();
    int best_value = 0;
    for (int val

<details>
<summary>英文:</summary>

Main idea of my solution is simple BFS. For a given subset you start with an initial configuration of 0-1 modifiers having an associated value (sum on the left hand side of your equation) and cost (sum of modifiers). In each step the cheapest configuration is extracted from a queue and each of its neighbors (adjacent by increasing a single modifier) is considered.

A few necessary observations. If there are several configurations producing the same value, only one of those with the minimum cost needs to be considered, so each distinct value will be placed in a queue at most once. We don&#39;t have to add a negative modifier if we are below target range and we don&#39;t have to add a positive modifier if we are above, so search space is trivially bounded. 

This gives a solution that constructs minimum cost configuration for a given range `R = [from, to]` and a mask in `O(max(|from|, |to|))` memory and time. Note that while solving for any given range we will encounter many solutions for others queries and it is wasteful to discard them.


----------


Implementation example #1, C++, solving each query from scratch:
```cpp
#include &lt;array&gt;
#include &lt;iostream&gt;
#include &lt;limits&gt;
#include &lt;numeric&gt;
#include &lt;queue&gt;
#include &lt;vector&gt;

constexpr int N = 7;

// this corresponds to subset ordering on the screenshot
constexpr std::array&lt;int, N&gt; coef{-42, 75, -30, 80, 25, 50, 280};

struct Solution {
  int lhs;
  std::array&lt;int, N&gt; mods;
};

Solution solve(int mask, int l, int r) {
  Solution init{};
  int low = std::numeric_limits&lt;int&gt;::max(), high = std::numeric_limits&lt;int&gt;::min();
  // int g = 0, neg = 0, pos = 0;
  for (int i = 0; i &lt; N; ++i) if (mask &amp; 1 &lt;&lt; i) {
    // g = std::gcd(g, coef[i]);
    // neg += coef[i] &lt; 0;
    // pos += coef[i] &gt; 0;
    init.lhs += coef[i];
    init.mods[i] = 1;
    low = std::min(low, r + 1 + coef[i]);
    high = std::max(high, l - 1 + coef[i]);
  }
  if (l &lt;= init.lhs &amp;&amp; init.lhs &lt;= r) {
    return init;
  }
  // if (g == 0 || r - (r % g + g) % g &lt; l || l &gt; 0 &amp;&amp; pos == 0 || r &lt; 0 &amp;&amp; neg == 0) {
  //   return {l - 1, {}};
  // }
  low = std::min(low, init.lhs);
  high = std::max(high, init.lhs);
  std::queue&lt;int&gt; q;
  q.push(init.lhs - low);
  std::vector&lt;int8_t&gt; last_move(high - low + 1);
  last_move[init.lhs - low] = -1;
  int restore_from = 0;
  l -= low, r -= low;
  while (!q.empty()) {
    int cur_val = q.front();
    q.pop();
    // #pragma GCC unroll 7
    for (int i = 0; i &lt; N; ++i) if (mask &amp; 1 &lt;&lt; i) {
      if (coef[i] &lt; 0? cur_val &lt; l: cur_val &gt; r) {
        continue;
      }
      int next_val = cur_val + coef[i];
      if (last_move[next_val]) {
        continue;
      }
      last_move[next_val] = i + 1;
      if (l &lt;= next_val &amp;&amp; next_val &lt;= r) {
        restore_from = next_val;
        q = {};
        break;
      }
      q.push(next_val);
    }
  }
  if (l &gt; restore_from || restore_from &gt; r) {
    return {l + low - 1, {}};
  }
  init.lhs = restore_from + low;
  while (last_move[restore_from] != -1) {
    ++init.mods[last_move[restore_from] - 1];
    restore_from -= coef[last_move[restore_from] - 1];
  }
  return init;
}

int main() {
  int64_t sum = 0;
  for (int R = -5000; R &lt;= 5000; ++R) {
    for (int mask = 0; mask &lt; 1 &lt;&lt; N; ++mask) if (auto res = solve(mask, R, R); res.lhs == R) {
      sum += std::accumulate(res.mods.begin(), res.mods.end(), 0);

      // this prints unit range, subset, solution cost and solution itself
      // std::cout &lt;&lt; &#39;=&#39; &lt;&lt; R &lt;&lt; &quot; #&quot; &lt;&lt; mask + 1 &lt;&lt; &quot;: &quot; &lt;&lt; std::accumulate(res.mods.begin(), res.mods.end(), 0) &lt;&lt; &#39;\n&#39;;
      // for (auto x: res.mods) {
      //   std::cout &lt;&lt; &#39; &#39; &lt;&lt; +x;
      // }
      // std::cout &lt;&lt; &#39;\n&#39;;
    }
  }
  std::cout &lt;&lt; sum &lt;&lt; &#39;\n&#39;;
}

Commented lines of code inside solve are minor optimizations that improve running time ~twice if uncommented. This is not the most optimized implementation of this approach, because the other somewhat faster version I have is less readable and AFAIK impossible to translate to C#. Without them this code runs on my current machine in ~6s, solving for each unit range from -5000 to 5000 independently.

---

Implementation example #2, C++, precomputing minimum cost for each unit range (from == to):

#include <algorithm>
#include <array>
#include <cassert>
#include <iostream>
#include <limits>
#include <numeric>
#include <queue>
#include <vector>

constexpr int N = 7;

// this corresponds to subset ordering on the screenshot in the question
constexpr std::array<int, N> coef{-42, 75, -30, 80, 25, 50, 280};

struct Solution {
  int lhs;
  std::array<int, N> mods;
};

class Precalc {
public:
  Precalc(int min_R, int max_R)
      : min_R{min_R},
        max_R{max_R},
        low_val{std::min({min_R, 0, min_R + 1 + *std::min_element(coef.begin(), coef.end())})},
        high_val{std::max({max_R, 0, max_R - 1 + *std::max_element(coef.begin(), coef.end())})},
        last_move{},
        cost{} {
    for (int mask = 0; mask < 1 << N; ++mask) {
      last_move[mask].resize(high_val - low_val + 1);
      cost[mask].resize(high_val - low_val + 1);
      do_precalc(mask);
    }
  }

  Solution get_solution(int mask, int from, int to) const {
    assert(min_R <= from && from <= to && to <= max_R);
    int best_cost = std::numeric_limits<int>::max();
    int best_value = 0;
    for (int val = from; val <= to; ++val) {
      if (last_move[mask][val - low_val] != 0 && best_cost > cost[mask][val - low_val]) {
        best_cost = cost[mask][val - low_val];
        best_value = val;
      }
    }
    if (best_cost == std::numeric_limits<int>::max()) {
      return {from - 1, {}};
    }
    Solution res{best_value, {}};
    int restore_from = best_value;
    while (last_move[mask][restore_from - low_val] != -1) {
      ++res.mods[last_move[mask][restore_from - low_val] - 1];
      restore_from -= coef[last_move[mask][restore_from - low_val] - 1];
    }
    for (int i = 0; i < N; ++i) if (mask & 1 << i) {
      ++res.mods[i];
    }
    return res;
  }

private:
  void do_precalc(int mask) {
    int init = 0;
    for (int i = 0; i < N; ++i) if (mask & 1 << i) {
      init += coef[i];
    }
    if (low_val > init || init > high_val) {
      return;
    }
    std::queue<int> q;
    q.push(init);
    last_move[mask][init - low_val] = -1;
    while (!q.empty()) {
      int cur_val = q.front();
      q.pop();
      for (int i = 0; i < N; ++i) if (mask & 1 << i) {
        int next_val = cur_val + coef[i];
        if (low_val > next_val || next_val > high_val || last_move[mask][next_val - low_val] != 0) {
          continue;
        }
        last_move[mask][next_val - low_val] = i + 1;
        cost[mask][next_val - low_val] = cost[mask][cur_val - low_val] + 1;
        q.push(next_val);
      }
    }
  }

  int min_R, max_R;
  int low_val, high_val;
  std::array<std::vector<int8_t>, 1 << N> last_move;
  std::array<std::vector<uint16_t>, 1 << N> cost;
};

int main() {
  int min_R = -50000, max_R = 50000;
  Precalc precalc{min_R, max_R};
  int64_t sum = 0;
  for (int R = min_R; R <= max_R; ++R) {
    for (int mask = 0; mask < 1 << N; ++mask) {
      if (auto res = precalc.get_solution(mask, R, R); res.lhs == R) {
        sum += std::accumulate(res.mods.begin(), res.mods.end(), 0);
      }
      int from = std::max(R - 50, min_R), to = std::min(R + 50, max_R);
      if (auto res = precalc.get_solution(mask, from, to); res.lhs >= from) {
        assert(res.lhs <= to);
        sum += std::accumulate(res.mods.begin(), res.mods.end(), 0);
      }
    }
  }
  std::cout << sum << '\n';
}

Precomputation itself takes less than a second and occupies ~37 megabytes. The whole program, solving for 200002 ranges, half of them length 1 and half — length 101, takes 40s.

Note that this implementation is still quite silly. We still take O(max(|from|, |to|)) time to restore a configuration, although with much better constant factor. It is trivial to memoize full configurations instead of merely the cost and the last move and answer each query in O(to - from), but this will increase memory footprint ~6 times and contradicts one of the requirements, being a "list of precomputed solutions". If something like that is desired, only a part of configurations could be memoized instead, for example all (optimal) configurations with costs divisible by 16, stored in a hash table.