टग ऑफ वॉर एल्गोरिदम

इस समस्या में पूर्णांकों का एक सेट दिया गया है, हमें उन्हें दो भागों में तोड़ना है, ताकि दो सबसेट के योग का अंतर जितना संभव हो उतना न्यूनतम हो। इसलिए हमारा लक्ष्य टग ऑफ वॉर गेम में भाग लेने के लिए लगभग समान ताकत के दो समूहों में विभाजित करना है।

यदि सबसेट n का आकार सम है, तो इसे n/2 में विभाजित किया जाना चाहिए, लेकिन n के विषम मान के लिए, एक सबसेट का आकार (n-1)/2 होना चाहिए, और दूसरे सबसेट का आकार (n+1)/2 होना चाहिए।

इनपुट और आउटपुट

इनपुट: अलग-अलग वजन का एक सेट। {23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4} आउटपुट: वजन वितरित करने के लिए लेफ्ट और राइट सबसेट ताकि अंतर न्यूनतम हो। लेफ्ट: {45, -34, 12, 98, -1} राइट: {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  #include 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

आउटपुट
Left: 45 -34 12 98 -1 Right: 23 0 -99 4 189 4