টাগ অফ ওয়ার অ্যালগরিদম

এই সমস্যাটিতে পূর্ণসংখ্যার একটি সেট দেওয়া হয়েছে, আমাদের সেগুলিকে দুটি ভাগে ভাগ করতে হবে, যেমন দুটি উপসেটের যোগফলের পার্থক্য যতটা সম্ভব ন্যূনতম। তাই টাগ অফ ওয়ার গেমে অংশগ্রহণের জন্য আমাদের লক্ষ্য প্রায় সমান শক্তির দুটি দলকে ভাগ করা।

যদি 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