रस्साकशी एल्गोरिथम

इस समस्या में पूर्णांकों का एक सेट दिया गया है, हमें उन्हें दो भागों में तोड़ना है, ताकि दो उपसमुच्चयों के योग का अंतर यथासंभव न्यूनतम हो। इसलिए हमारा लक्ष्य रस्साकशी के खेल में भाग लेने के लिए लगभग समान शक्ति वाले दो समूहों को विभाजित करना है।

यदि उपसमुच्चय 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