Thuật toán kéo co

Trong bài toán này cho trước một tập các số nguyên, chúng ta phải chia chúng thành hai phần sao cho hiệu của tổng của hai tập con là nhỏ nhất có thể. Vì vậy, mục tiêu của chúng tôi là chia hai nhóm có sức mạnh gần bằng nhau để tham gia trò chơi Kéo co.

Nếu kích thước của tập hợp con n là chẵn, thì nó phải được chia thành n / 2, nhưng đối với giá trị lẻ của n, thì kích thước của một tập hợp con phải là (n-1) / 2 và kích thước của một tập hợp con khác phải là ( n + 1) / 2.

Đầu vào và Đầu ra

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}

Thuật toán

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

Đầu vào - Tập hợp các trọng số đã cho, số trọng số, danh sách hiện tại, số mục đã chọn, hiệu số giữa hai tổng tập hợp con, tổng của tất cả các mục, tổng trong tập hợp con, vị trí của phần tử đã chọn.

Đầu ra - Bộ giải pháp đã chọn cho các tập hợp con bên trái và bên phải.

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

Ví dụ

#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);
}

Đầu ra

Left: 45 -34 12 98 -1
Right: 23 0 -99 4 189 4