如何解决这个算术C++
How to Solve this arithmetic c++
我有一些元素，比如
5, 3, 7
和初始 int A （例如第一种情况下为 5）。我必须对数组元素中的这个数字进行加法和减法，以获得小于或等于 M（在本例中为 10）的最大数字。中间操作的结果不能超过 M 。我只能使用一次数组元素。
例如，这种情况的解决方案是
A = 5
A - 5 = 0
0 + 3 = 3
3 + 7 = 10
10等于M，最终结果
用什么算法可以解决这个问题？我正在用 C++ 编写这个程序。
这是一个可能的算法：
A = 5
M = 10
highest number = 0
array of numbers = {5, 3, 7}
function()
call recursive function(empty string, index 0, A)
print highest number
recursive function(string of operations used so far, int current element index, int sum so far)
if the length of the string of operations == number of ints in array
if sum so far > highest number
highest number = sum so far
return
B = sum so far + current element
C = sum so far - current element
if B <= M
recursive function(string of operations plus appended '+', int current element index + 1, B)
if C <= M
recursive function(string of operations plus appended '-', int current element index + 1, C)
基本思想：使用递归来跟踪加减运算。在这里，我只是将 + 和 - 附加到一个字符串，当字符串达到数组的大小时，我检查总和是否高于当前最大值。您可以在 Java here 中看到完成的演示。随意玩一下演示中的数字，看看它是如何工作的。
我认为没有 "smart" 算法可以在线性甚至多项式时间内解决这个问题。恐怕唯一可行的方法是尝试所有可能的组合，然后选择最好的一个。不过，您可以使用一些概念上类似于 branch and bound 的技术来更快地获得结果。
我会这样做。
基本算法
首先，我会生成所有可能的组合。对于您的 N 个数字中的每一个，您都可以选择对它求和或对其进行减法，因此您有 2 个选择。这意味着您总共有 2^N 种可能的选择。在您的示例中，N=3，这些将是：---、--+、-+-、-++、+--、+-+、++-、+++。 （这就像用二进制计数，从 0 = 000 到 7 = 111）。
此时你必须"execute"每个序列。使用这些数字 (5, 3, 7)，第一个序列表示 -5 -3 -7。您必须 运行 一次一个步骤，并且每次检查您没有超过目标 M，因为它是必需的。由于您的初始值 A 是 5，这将导致：5-5=0，并且由于 0<10 您可以继续。那么，0-3=-3，小于10，就可以了。然后，-3-7=-10，因为这是最后一个操作，我们不必检查它是否小于 10。所以序列是有效的，我们得到 --- 结果是 - 10.这是迄今为止最好的结果（因为它是唯一的），所以让我们将序列保存为最佳序列和最终结果。
那么，让我们进入下一个序列，--+。再次有效，最终结果为4。这是迄今为止最好的结果，所以我们可以保存这个序列--+，覆盖之前的最好结果。
继续，在-++我们会找到最好的结果，10，无法改进，因此我们可以停在那里。如果我们没有达到 M，我们必须评估所有序列，最后我们将拥有最好的一个。可能有不止一个导致最好的结果，例如，如果你有重复的数字（3 3 可以是 +3 -3 或 -3 +3，序列不同但结果显然是相同的)，因此您可能希望将最佳解决方案存储在一个向量中，而不是只保留一个。
这就是基本算法。现在，让我们试着优化一下。
优化算法
到目前为止，我们已经生成了所有可能的序列（从 --- 到 +++），并一次对它们进行了评估。但在某些情况下，对它们全部进行评估是浪费时间。例如，假设初始数字再次为 A=5，目标为 M=10。如果序列类似于 6 3 4，在某个点我们会尝试计算 +--，但那会立即失败，因为第一个中间结果会超过最大值 (5+6=11)。按照基本算法，我们将继续评估 +-+，但它没有意义：它显然会失败，出于同样的原因，在相同的步骤（第一个数字，即 5+6） .以+开头的无效序列，后面所有的符号选择都无所谓：所有以+开头的序列必然无效，可以舍弃.所以这意味着如果我们找到一个无效的序列，我们可以丢弃所有其他以它开头的序列。
为此，我们可以将所有序列保存在一棵树中，该树将符号的每个选择与前一个符号相关联。然后，一旦我们找到一个无效的解决方案，我们就可以丢弃所有其他以该解决方案开头的解决方案。例如，树可以这样保存：
Root
/ \
/ \
/ \
/ \
/ \
- +
/ \ / \
- + - +
/ \ / \ / \ / \
- + - + - + - +
并且每个序列对应于必须探索才能到达其中一个叶子的一系列节点。当您访问树时，对于每个节点，您可以计算并存储到目前为止的序列值。因此，当您到达第一层的 + 时，您会看到 5+6=11，这太多了，您将整个节点标记为无效，从而避免探索所有可能的变体。当然，对于 N=3 个数字，它不会有太大区别，因为总共只有 2^3=8 个序列。但是对于 N=20，它们将是一百万，并且节省的时间可能会很可观。
我有一些元素，比如
5, 3, 7
和初始 int A （例如第一种情况下为 5）。我必须对数组元素中的这个数字进行加法和减法，以获得小于或等于 M（在本例中为 10）的最大数字。中间操作的结果不能超过 M 。我只能使用一次数组元素。
例如，这种情况的解决方案是
A = 5
A - 5 = 0
0 + 3 = 3
3 + 7 = 10
10等于M，最终结果
用什么算法可以解决这个问题？我正在用 C++ 编写这个程序。
这是一个可能的算法：
A = 5
M = 10
highest number = 0
array of numbers = {5, 3, 7}
function()
call recursive function(empty string, index 0, A)
print highest number
recursive function(string of operations used so far, int current element index, int sum so far)
if the length of the string of operations == number of ints in array
if sum so far > highest number
highest number = sum so far
return
B = sum so far + current element
C = sum so far - current element
if B <= M
recursive function(string of operations plus appended '+', int current element index + 1, B)
if C <= M
recursive function(string of operations plus appended '-', int current element index + 1, C)
基本思想：使用递归来跟踪加减运算。在这里，我只是将 + 和 - 附加到一个字符串，当字符串达到数组的大小时，我检查总和是否高于当前最大值。您可以在 Java here 中看到完成的演示。随意玩一下演示中的数字，看看它是如何工作的。
我认为没有 "smart" 算法可以在线性甚至多项式时间内解决这个问题。恐怕唯一可行的方法是尝试所有可能的组合，然后选择最好的一个。不过，您可以使用一些概念上类似于 branch and bound 的技术来更快地获得结果。
我会这样做。
基本算法
首先，我会生成所有可能的组合。对于您的 N 个数字中的每一个，您都可以选择对它求和或对其进行减法，因此您有 2 个选择。这意味着您总共有 2^N 种可能的选择。在您的示例中，N=3，这些将是：---、--+、-+-、-++、+--、+-+、++-、+++。 （这就像用二进制计数，从 0 = 000 到 7 = 111）。
此时你必须"execute"每个序列。使用这些数字 (5, 3, 7)，第一个序列表示 -5 -3 -7。您必须 运行 一次一个步骤，并且每次检查您没有超过目标 M，因为它是必需的。由于您的初始值 A 是 5，这将导致：5-5=0，并且由于 0<10 您可以继续。那么，0-3=-3，小于10，就可以了。然后，-3-7=-10，因为这是最后一个操作，我们不必检查它是否小于 10。所以序列是有效的，我们得到 --- 结果是 - 10.这是迄今为止最好的结果（因为它是唯一的），所以让我们将序列保存为最佳序列和最终结果。
那么，让我们进入下一个序列，--+。再次有效，最终结果为4。这是迄今为止最好的结果，所以我们可以保存这个序列--+，覆盖之前的最好结果。
继续，在-++我们会找到最好的结果，10，无法改进，因此我们可以停在那里。如果我们没有达到 M，我们必须评估所有序列，最后我们将拥有最好的一个。可能有不止一个导致最好的结果，例如，如果你有重复的数字（3 3 可以是 +3 -3 或 -3 +3，序列不同但结果显然是相同的)，因此您可能希望将最佳解决方案存储在一个向量中，而不是只保留一个。
这就是基本算法。现在，让我们试着优化一下。
优化算法
到目前为止，我们已经生成了所有可能的序列（从 --- 到 +++），并一次对它们进行了评估。但在某些情况下，对它们全部进行评估是浪费时间。例如，假设初始数字再次为 A=5，目标为 M=10。如果序列类似于 6 3 4，在某个点我们会尝试计算 +--，但那会立即失败，因为第一个中间结果会超过最大值 (5+6=11)。按照基本算法，我们将继续评估 +-+，但它没有意义：它显然会失败，出于同样的原因，在相同的步骤（第一个数字，即 5+6） .以+开头的无效序列，后面所有的符号选择都无所谓：所有以+开头的序列必然无效，可以舍弃.所以这意味着如果我们找到一个无效的序列，我们可以丢弃所有其他以它开头的序列。
为此，我们可以将所有序列保存在一棵树中，该树将符号的每个选择与前一个符号相关联。然后，一旦我们找到一个无效的解决方案，我们就可以丢弃所有其他以该解决方案开头的解决方案。例如，树可以这样保存：
Root
/ \
/ \
/ \
/ \
/ \
- +
/ \ / \
- + - +
/ \ / \ / \ / \
- + - + - + - +
并且每个序列对应于必须探索才能到达其中一个叶子的一系列节点。当您访问树时，对于每个节点，您可以计算并存储到目前为止的序列值。因此，当您到达第一层的 + 时，您会看到 5+6=11，这太多了，您将整个节点标记为无效，从而避免探索所有可能的变体。当然，对于 N=3 个数字，它不会有太大区别，因为总共只有 2^3=8 个序列。但是对于 N=20，它们将是一百万，并且节省的时间可能会很可观。