Thuật toán Kéo co (Tug of War) chia tập cân bằng

Giới thiệu

Cho tập số nguyên, chia thành hai tập con sao cho hiệu tổng hai tập nhỏ nhất. Mục tiêu: chia hai nhóm sức mạnh gần bằng nhau cho trò chơi kéo co.

Nếu n chẵn: mỗi tập n/2 phần tử. Nếu n lẻ: một tập (n-1)/2, tập kia (n+1)/2.

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

Đầu vào: Tập trọng số: {23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4}
Đầu ra:
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 trọng số, số lượng, danh sách hiện tại, số đã chọn, giải pháp, hiệu số, tổng tất cả, tổng tập con, vị trí.

Đầu ra: Tập giải pháp cho hai bên.

Begin
  nếu pos = n thì return
  nếu (n/2 - select) > (n - pos) thì return
  tugOfWar(weight, n, curr, select, sol, diff, sum, total, pos+1)
  select := select + 1
  total := total + weight[pos]
  curr[pos] := true
  nếu select = n/2 thì
    nếu |sum/2 - total| < diff thì
      diff := |sum/2 - total|
      với i := 0 đến n làm: sol[i] := curr[i]
  ngược lại tugOfWar(weight, n, curr, select, sol, diff, sum, total, pos+1)
  curr[pos] := false
End

Ví dụ (C++)

#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) 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]) cout << arr[i] << " ";
  cout << endl << "Right: ";
  for (int i = 0; i < n; i++) if (!soln[i]) cout << arr[i] << " ";
}

int main() {
  int weight[] = {23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4};
  int n = 11;
  findSolution(weight, n);
}

Kết quả đầu ra

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