C++ 拔河

在本文中，我们将通过示例讨论 C++ 中的拔河问题。

计算机科学和数学中最著名的问题之一是拔河。它通常被称为平衡问题。在此任务中，我们有一组权重，目标是将它们分成两个尽可能平均的组，同时最小化两个组的总权重之间的差异。请按照以下步骤解决拔河问题。

• 将一组n 个整数分成两个大小分别为n/2的子集，使两个子集之间的绝对差尽可能小。如果 n 是奇数，一个子集的大小必须是(n-1)/2，第二个子集的大小必须是(n+1)/2。如果n是偶数，则两个子集的大小都必须严格为n/2。
• 例如，考虑以下集合：3, 4, 5, -3, 100, 1, 89, 54, 23, 20。此集合的大小为10。此集合应提供输出 4, 100, 1, 23, 20 和 3, 5, -3, 89, 54。两个输出子集的大小均为 5，它们的元素总和相同（148 和 148）。
• 再考虑一个n为奇数的例子。为此集合赋予以下值：23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4。建议的输出子集为 45, -34, 12, 98, -1 和 23, 0, -99, 4, 189, 4。两个子集中的元素总和分别为120和121。
• 下一个方法尝试每个可能的半大小子集。如果只生成了一个半大小的子集，则其余元素构成另一个子集。我们从一个空集开始，然后逐个构建它。每个元素都可以是当前集的一部分，也可以是剩余元素（另一个子集）的一部分。我们考虑每个组成部分的两种情况。我们确定此解决方案是否优于到目前为止的最佳解决方案，直到当前集的大小达到n/2。如果是，则我们更新最佳解决方案。
• 下面给出了拔河问题的解决方案。它输出所需的数组。

解释：-

在检查了所有可能的组合后，最合适的两个子序列是

• 12 , 18 , 25
• 15, 10, 20, 8

1. 第一个子序列的所有元素之和为55，而第二个子序列的所有元素之和为53，两者之和的差仅为2，这是最小差值；因此，这两个就是结果子序列。
2. 在此拔河问题中，我们必须检查输入数组大小一半的每个可行子序列，然后剩余的组件将构成另一个子序列。使用布尔数组，我们将考虑每个元素在其各自子序列中的位置。如果在过程中当前子集的大小等于输入数组的一半，我们必须确定最佳解决方案是否可用。

算法步骤

步骤 1：创建一个名为“getResult()”的函数，该函数接受两个参数：“input”的整数向量和该向量的大小。

步骤 2：在此“getResult()”函数中，必须初始化两个布尔数组，名为 'temp' 和 'res'，以及两个整数变量“mini”和“sum”。

步骤 3：使用 'i' 变量，通过 for 循环迭代，将所有输入组件的总和赋给 'sum'，并将 'false' 值赋给布尔数组 'temp' 和 'res'。

步骤 4：创建一个名为“helper”的函数，该函数接受九个参数：名为“input”的整数向量、向量的大小。一个名为“temp”的布尔数组、数字零，表示已选元素的总数，一个名为“res”的第二个布尔数组、整数变量“mini”、整数变量“sum”、整数变量“curr_sum”以及整数变量“cur_Index + 1”。

步骤 5：在此“helper”函数中，将“selected”的值增加，将“input”中“cur_Index”处的元素值添加到“cur_sum”，并将“temp”中“cur_Index”处的元素值赋为“true”。

步骤 6：检查 selected 的值是否等于向量大小的一半，

• 如果相等，最佳做法是确定“sum / 2”与“curr_sum”的绝对差值是否小于“mini”，如果是，则将该值赋给“mini”，并通过 for 循环将整个 temp 数组赋给“res”数组。
• 如果不是，则在修改参数后，按代码中所示重复调用 helper 方法。

步骤 7：将 temp 布尔数组的“cur_Index”赋为“false”。

步骤 8：打印整个序列。

程序

让我们看一个例子来演示 C++ 中的拔河问题

输出

复杂度

时间复杂度：O(2 ^ N)

在调用“getResult()”时，我们还调用了“helper”函数，并且在 helper 函数中，我们使用递归调用来检查所有有效的选项以创建这两个子序列。因此，总时间复杂度为O(2 ^ N)。

空间复杂度：O(N)

由于我们使用“N”的额外空间来存储二叉树，因此总空间复杂度为O(N)。

C++ 中拔河的好处

“双指针技术”或“两数之和问题”，也称为拔河，是一种常见的算法技术，用于计算机科学和编程，尤其是在 C++ 和类似编程语言中。它不是 C++ 中的一项功能或库，而是一种有效解决特定类型问题的方法。以下是应用 C++ 中拔河方法的一些优点：

1. 效率：在数组或其他数据结构中查找匹配项对时，通常使用拔河技术来找到解决方案。其时间复杂度为O(N)，其中N是输入数据的大小，通常效率很高。
2. 优化：当你需要找出最接近的项对、具有特定总和的两个元素，或将数组分成两组且总和差异最小的方法时，这项技术非常有用。
3. 内存效率：拔河是一种内存高效的问题解决方法，因为它通常为变量和指针使用固定量的内存。
4. 简单性：一旦我们掌握了拔河技术的基本原理，就可以在 C++ 代码中实现和应用。其实现和应用都很简单。
5. 多功能性：这项技术可以用于解决各种问题，包括涉及数组、链表和其他数据结构的问题。它不限于特定的数据或问题领域。
6. 避免嵌套循环：嵌套循环的效率可能较低，并且在代码复杂性方面更难管理；在某些情况下，使用拔河可以帮助你避免使用它们。
7. 降低时间复杂度：拔河可用于将某些问题的O(N2)（二次时间）时间复杂度转换为O(N)（线性时间）时间复杂度，从而大大提高方法的效率。

结论

虽然拔河技术有很多优点，但重要的是要记住，并非所有情况都可以用它来解决。评估当前问题，并决定此方法是否适用于你的特定用例。此外，掌握这项策略可能需要算法问题解决方面的实践和专业知识。