拔河问题
什么是拔河问题？
在拔河问题中，给定一组整数，我们的任务是将它们分成两部分，使得两个子集之和的差尽可能小。换句话说，将集合分成两组实力相等的组，参与拔河比赛。当集合的大小为偶数时，将其分成两部分会更容易。如果集合中包含奇数个元素，则很难做到这一点。因此，划分时需要定义一些约束。
如果子集 N 的大小为偶数，则可以使用 N/2 将其分成两部分；但对于 N 的奇数，一个子集的大小必须为 (N-1)/2，另一个子集的大小必须为 (N+1)/2。
使用回溯法解决拔河问题
假设给定集合的大小为奇数 −
集合 = {23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4}
当我们分配权重以使差异最小时，得到的子集将是−
左：{45, -34, 12, 98, -1}
右：{23, 0, -99, 4, 189, 4}
以下步骤解释了如何使用回溯方法解决拔河问题 −
首先创建一个空子集，记作 left。
用原始集合中所需数量的元素填充此空子集。所需元素数量取决于原始集合的大小。如果子集大小为奇数，则应填充 (N-1)/2 个元素；如果子集大小为偶数，则子集大小应为 N/2。
检查填充元素的差值是否符合给定的约束条件。如果符合，则将其标记为解决方案的一部分。
如果差值不是最小，请尝试其他组合并更新现有解决方案。
第一个子集填充完成后，剩余元素将自动成为第二个子集的一部分。
示例
在下面的示例中，我们将实际演示如何解决拔河问题。
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h>
#include <math.h>
void tgOfWarSoln(int* weight, int n, bool curr[], int select, bool sol[], int *diff, int sum, int total, int pos) {
//当pos覆盖所有权重时
if (pos == n)
return;
//剩余元素必须大于所需结果
if ((n/2 - select) > (n - pos))
return;
tgOfWarSoln(weight, n, curr, select, sol, diff, sum, total, pos+1);
select++;
total += weight[pos];
//将当前元素添加到解中
curr[pos] = true;
//当解形成时
if (select == n/2) {
//检查它是否是更好的解
if (abs(sum/2 - total) < *diff) {
*diff = abs(sum/2 - total);
for (int i = 0; i<n; i++)
sol[i] = curr[i];
}
} else {
tgOfWarSoln(weight, n, curr, select, sol, diff, sum, total, pos+1);
}
//当没有正确完成时，删除当前元素
curr[pos] = false;
}
void checkSolution(int *arr, int n) {
bool* curr = (bool*)malloc(n*sizeof(bool));
bool* soln = (bool*)malloc(n*sizeof(bool));
//最初将最小差异设置为无穷大
int diff = INT_MAX;
int sum = 0;
for (int i=0; i<n; i++) {
//求所有元素的总和
sum += arr[i];
//使所有元素为 false
curr[i] = soln[i] = false;
}
tgOfWarSoln(arr, n, curr, 0, soln, &diff, sum, 0, 0);
printf("Left: ");
for (int i=0; i<n; i++)
if (soln[i] == true)
printf("%d ", arr[i]);
printf("
Right: ");
for (int i=0; i<n; i++)
if (soln[i] == false)
printf("%d ", arr[i]);
printf("
");
free(curr);
free(soln);
}
int main() {
int weight[] = {23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4};
int n = 11;
checkSolution(weight, n);
return 0;
}
#include <iostream>
#include <cmath>
#include <climits>
using namespace std;
void tgOfWarSoln(int* weight, int n, bool curr[], int select, bool sol[], int &diff, int sum, int total, int pos) {
//当pos覆盖所有权重时
if (pos == n)
return;
//左边元素必须大于所需结果
if ((n/2 - select) > (n - pos))
return;
tgOfWarSoln(weight, n, curr, select, sol, diff, sum, total, pos+1);
select++;
total += weight[pos];
//将当前元素添加到解决方案中
curr[pos] = true;
//when solution is formed
if (select == n/2) {
//检查这是否是更好的解决方案
if (abs(sum/2 - total) < diff) {
diff = abs(sum/2 - total);
for (int i = 0; i<n; i++)
sol[i] = curr[i];
}
} else {
tgOfWarSoln(weight, n, curr, select, sol, diff, sum, total, pos+1);
}
//如果操作不正确，则删除当前元素
curr[pos] = false;
}
void checkSolution(int *arr, int n) {
bool* curr = new bool[n];
bool* soln = new bool[n];
//最初将最小差异设置为无穷大
int diff = INT_MAX;
int sum = 0;
for (int i=0; i<n; i++) {
//求所有元素的总和
sum += arr[i];
//使所有元素为 false
curr[i] = soln[i] = false;
}
tgOfWarSoln(arr, n, curr, 0, soln, diff, sum, 0, 0);
cout << "Left: ";
for (int i=0; i<n; i++)
if (soln[i] == true)
cout << arr[i] << " ";
cout << endl << "Right: ";
for (int i=0; i<n; i++)
if (soln[i] == false)
cout << arr[i] << " ";
}
int main() {
int weight[] = {23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4};
int n = 11;
checkSolution(weight, n);
}
public class Main {
static void tgOfWarSoln(int[] weight, int n, boolean[] curr, int select, boolean[] sol, int[] diff, int sum, int total, int pos) {
//当 pos 覆盖所有权重时
if (pos == n)
return;
//左边元素必须大于所需结果
if ((n / 2 - select) > (n - pos))
return;
tgOfWarSoln(weight, n, curr, select, sol, diff, sum, total, pos + 1);
select++;
//将当前元素添加到解决方案中
total += weight[pos];
curr[pos] = true;
//when solution is formed
if (select == n / 2) {
//检查它是否是更好的解决方案
if (Math.abs(sum / 2 - total) < diff[0]) {
diff[0] = Math.abs(sum / 2 - total);
for (int i = 0; i < n; i++)
sol[i] = curr[i];
}
} else {
tgOfWarSoln(weight, n, curr, select, sol, diff, sum, total, pos + 1);
}
//如果操作不正确，则删除当前元素
curr[pos] = false;
}
static void checkSolution(int[] arr, int n) {
boolean[] curr = new boolean[n];
boolean[] soln = new boolean[n];
//最初将最小差异设置为无穷大
int[] diff = {Integer.MAX_VALUE};
int sum = 0;
for (int i = 0; i < n; i++) {
//求所有元素的总和
sum += arr[i];
//使所有元素为假
curr[i] = soln[i] = false;
}
tgOfWarSoln(arr, n, curr, 0, soln, diff, sum, 0, 0);
System.out.print("Left: ");
for (int i = 0; i < n; i++)
if (soln[i] == true)
System.out.print(arr[i] + " ");
System.out.println();
System.out.print("Right: ");
for (int i = 0; i < n; i++)
if (soln[i] == false)
System.out.print(arr[i] + " ");
}
public static void main(String[] args) {
int[] weight = {23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4};
int n = 11;
checkSolution(weight, n);
}
}
def tgOfWarSoln(weight, n, curr, select, sol, diff, sum, total, pos):
if pos == n:
return
if (n // 2 - select) > (n - pos):
return
tgOfWarSoln(weight, n, curr, select, sol, diff, sum, total, pos + 1)
select += 1
total += weight[pos]
curr[pos] = True
if select == n // 2:
if abs(sum // 2 - total) < diff[0]:
diff[0] = abs(sum // 2 - total)
for i in range(n):
sol[i] = curr[i]
else:
tgOfWarSoln(weight, n, curr, select, sol, diff, sum, total, pos + 1)
curr[pos] = False
def checkSolution(arr, n):
curr = [False] * n
soln = [False] * n
diff = [float('inf')]
sum = 0
for i in range(n):
sum += arr[i]
curr[i] = soln[i] = False
tgOfWarSoln(arr, n, curr, 0, soln, diff, sum, 0, 0)
print("Left: ", end="")
for i in range(n):
if soln[i] == True:
print(arr[i], end=" ")
print()
print("Right: ", end="")
for i in range(n):
if soln[i] == False:
print(arr[i], end=" ")
weight = [23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4]
n = 11
checkSolution(weight, n)
输出
Left: 45 -34 12 98 -1 Right: 23 0 -99 4 189 4
