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

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

যদি সাবসেটের সাইজ n সম হয়, তবে সেটিকে n/2 করে ভাগ করতে হবে, কিন্তু n-এর বিষম মান হলে, একটি সাবসেটের সাইজ (n-1)/2, আরেকটির সাইজ (n+1)/2 হবে।

ইনপুট এবং আউটপুট

ইনপুট: ভিন্ন ওয়েটের একটি সেট। {23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4} আউটপুট: ওয়েট বন্টন করার জন্য লেফট এবং রাইট সাবসেট যাতে পার্থক্য ন্যূনতম হয়। Left: {45, -34, 12, 98, -1} Right: {23, 0, -99, 4, 189, 4}

অ্যালগরিদম

tugOfWar(weight, n, curr, select, sol, diff, sum, total, pos)

ইনপুট - দেওয়া ওয়েটের সেট, ওয়েটের সংখ্যা, কারেন্ট লিস্ট, সিলেক্টেড আইটেম সংখ্যা, দুটি সাবসেটের যোগফলের পার্থক্য, সব আইটেমের যোগফল, সাবসেটে টোটাল, সিলেক্টেড এলিমেন্টের পজিশন।

আউটপুট - লেফট এবং রাইট সাবসেটের জন্য সিলেক্টেড সলিউশন সেট।

শুরু
  যদি pos = n, তবে
    //যখন সব এলিমেন্ট নেওয়া হয়েছে
    রিটার্ন
  যদি (n/2-select) > (n - pos), তবে
    রিটার্ন
  tugOfWar(weight, n, curr, select, sol, diff, sum, total, pos+1)
  select := select + 1
  total := total + weight[pos]
  curr[pos] := true
    //যখন pos-এ আইটেম নেওয়া হয়
  যদি select = n/2, তবে
    যদি (sum/2 এবং total)-এর পার্থক্য < diff, তবে
      diff := (sum/2 এবং total)-এর পার্থক্য
      i := 0 থেকে n পর্যন্ত, করুন
        sol[i] := curr[i]
      শেষ
  অন্যথায়
    tugOfWar(weight, n, curr, select, sol, diff, sum, total, pos+1)
  curr[pos] := false
    //যদি ভালোভাবে না হয়, কারেন্ট এলিমেন্ট রিমুভ করুন
শেষ

উদাহরণ

#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) //যখন pos সব ওয়েট কভার করেছে return; if ((n/2 - select) > (n - pos)) //লেফট এলিমেন্ট রিকোয়ার্ড রেজাল্টের চেয়ে বড় হতে হবে return; tugOfWar(weight, n, curr, select, sol, diff, sum, total, pos+1); select++; total += weight[pos]; curr[pos] = true; //কারেন্ট এলিমেন্ট সলিউশনে যোগ করুন if (select == n/2) { //যখন সলিউশন ফর্ম হয় if (abs(sum/2 - total) < diff) { //চেক করুন কি এটি बेटার সলিউশন বা না 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; //যখন ভালোভাবে না হয়, কারেন্ট এলিমেন্ট রিমুভ করুন } void findSolution(int *arr, int n) { bool* curr = new bool[n]; bool* soln = new bool[n]; int diff = INT_MAX; //প্রাথমিকভাবে ন্যূনতম পার্থক্য ইনফিনিট সেট করুন int sum = 0; for (int i=0; i<n; i++) { sum += arr[i]; //সব এলিমেন্টের যোগফল বের করুন curr[i] = soln[i] = 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