줄다리기 알고리즘

이 문제에서는 정수 집합이 제공되므로 두 부분 집합의 합이 가능한 한 최소가 되도록 정수 집합을 두 부분으로 나누어야 합니다. 따라서 우리의 목표는 거의 같은 힘을 가진 두 그룹을 나누어 줄다리기 게임에 참여하는 것입니다.

부분집합 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