ชักเย่ออัลกอริทึม

ในปัญหานี้ จะมีการให้ชุดของจำนวนเต็ม เราต้องแยกพวกมันออกเป็นสองส่วน เพื่อให้ผลต่างของผลรวมของชุดย่อยสองชุดมีค่าน้อยที่สุด ดังนั้นเป้าหมายของเราคือแบ่งกลุ่มที่มีกำลังเกือบเท่ากันสองกลุ่มเพื่อเข้าร่วมในเกมชักเย่อ

หากขนาดของเซตย่อย 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