拔河算法
在这个问题中，给出了一组整数，我们必须将它们分为两部分，以使两个子集的和之差尽可能小。因此，我们的目标是将力量几乎相等的两组分成参加拔河比赛。
如果子集n的大小为偶数，则必须将其分为n/2，但对于n的奇数，则一个子集的大小必须为(n-1)/2，而另一个子集的大小必须为（n+1）/2。
输入输出
Input:
A set of different weights.
{23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4}
Output:
The left and right subset to distribute the weights to make the difference minimum.
Left: {45, -34, 12, 98, -1}
Right: {23, 0, -99, 4, 189, 4}算法
tugOfWar(weight, n, curr, select, sol, diff, sum, total, pos)
输入- 给定权重，权重数量，当前列表，所选项目的数量，两个子集总和之间的差，所有项目的总和，子集中的总和，所选元素的位置的集合。
输出- 为左右子集选择的解决方案集。
Begin
if pos = n, then //when all elements are taken
return
if (n/2-select) > (n - pos), then
return
tugOfWar(weight, n, curr, select, sol, diff, sum, total, pos+1)
select := select + 1
total := total + weight[pos]
curr[pos] := true //when item at pos is taken
if select = n/2, then
if difference of (sum/2 and total) < diff, then
diff := difference of (sum/2 and total)
for i := 0 to n, do
sol[i] := curr[i]
done
else
tugOfWar(weight, n, curr, select, sol, diff, sum, total, pos+1)
curr[pos] := false //remove current element if not properly done
End示例
#include <iostream>
#include<cmath>
using namespace std;
void tugOfWar(int* weight, int n, bool curr[], int select, bool sol[], int &diff, int sum, int total, int pos) {
if (pos == n) //when the pos is covered all weights
return;
if ((n/2 - select) > (n - pos)) //left elements must be bigger than required result
return;
tugOfWar(weight, n, curr, select, sol, diff, sum, total, pos+1);
select++;
total += weight[pos];
curr[pos] = true; //add current element to the solution
if (select == n/2) { //when solution is formed
if (abs(sum/2 - total) < diff) { //check whether it is better solution or not
diff = abs(sum/2 - total);
for (int i = 0; i<n; i++)
sol[i] = curr[i];
}
} else {
tugOfWar(weight, n, curr, select, sol, diff, sum, total, pos+1);
}
curr[pos] = false; //when not properly done, remove current element
}
void findSolution(int *arr, int n) {
bool* curr = new bool[n];
bool* soln = new bool[n];
int diff = INT_MAX; //set minimum difference to infinity initially
int sum = 0;
for (int i=0; i<n; i++) {
sum += arr[i]; //find the sum of all elements
curr[i] = soln[i] = false; //make all elements as false
}
tugOfWar(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;
findSolution(weight, n);
}输出结果
Left: 45 -34 12 98 -1 Right: 23 0 -99 4 189 4