拔河算法

在这个问题中，给出了一组整数，我们必须将它们分为两部分，以使两个子集的和之差尽可能小。因此，我们的目标是将力量几乎相等的两组分成参加拔河比赛。

如果子集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