Computer >> कंप्यूटर >  >> प्रोग्रामिंग >> प्रोग्रामिंग

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


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

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

  1. फोर्ड फुलकर्सन एल्गोरिथम

    फोर्ड-फुलकर्सन एल्गोरिथम का उपयोग किसी दिए गए ग्राफ में प्रारंभ शीर्ष से सिंक शीर्ष तक अधिकतम प्रवाह का पता लगाने के लिए किया जाता है। इस ग्राफ में हर किनारे की क्षमता है। स्रोत और सिंक नाम के दो शीर्ष दिए गए हैं। स्रोत शीर्ष में सभी बाहरी किनारे हैं, कोई अंदरूनी किनारा नहीं है, और सिंक में सभी अंदर

  1. फ्लोयड वारशाल एल्गोरिथम

    Floyd-Warshall एल्गोरिदम का उपयोग किसी दिए गए भारित ग्राफ से सभी जोड़ी सबसे छोटी पथ समस्या को खोजने के लिए किया जाता है। इस एल्गोरिथम के परिणामस्वरूप, यह एक मैट्रिक्स उत्पन्न करेगा, जो ग्राफ़ में किसी भी नोड से अन्य सभी नोड्स के लिए न्यूनतम दूरी का प्रतिनिधित्व करेगा। सबसे पहले, आउटपुट मैट्रिक्स

  1. एल्गोरिथम में चरण गणना विधि

    चरण गणना विधि एल्गोरिदम का विश्लेषण करने की विधि में से एक है। इस पद्धति में, हम गिनते हैं कि एक निर्देश कितनी बार क्रियान्वित हो रहा है। इससे हम एल्गोरिथम की जटिलता का पता लगाने की कोशिश करेंगे। मान लीजिए कि अनुक्रमिक खोज करने के लिए हमारे पास एक एल्गोरिदम है। मान लीजिए प्रत्येक निर्देश c1, c2,… ल