Задача о "перетягивании каната"

Не нашёл этой задачи отдельно в вики, но это одна из типовых проблем на поиск в возвратом, того же рода, что, например, задача о сумме подмножеств. Как правило, такие проблемы решаются рекурсивно.

В англоязычных источниках задача известна как Tug of War (Перетягивание каната), название связано с тем, что нужно, имея набор из из n целых чисел (в общем случае, конечно, необязательно целых), разделить его на два подмножества с размерностями n/2 каждое так, чтобы разность суммы двух подмножеств была наименьшей из возможных. Минимизируя эту величину, мы как бы уравниваем "силу двух команд", которые будут тянуть канат в разные стороны. Если n - чётное значение, то размеры двух подмножеств должны быть равны n/2, а если n нечётно, то размер одного подмножества будет (n-1)/2, а другого (n+1)/2.

Ниже показана реализация на C++, проверенная в консоли Visual Studio 2019.

#include <iostream> 
#include <cmath> 
using namespace std;

void search( int *arr, int n, bool *currentItems, int numberOfSelected,
             bool *inSolution, int *minDiff, int sum, int currentSum, int currentPos) {
 if (currentPos == n) return;
 if ((n / 2 - numberOfSelected) > (n - currentPos)) return;
 search(arr, n, currentItems, numberOfSelected,inSolution, minDiff, sum, currentSum, currentPos + 1);
 numberOfSelected++;
 currentSum = currentSum + arr[currentPos];
 currentItems[currentPos] = true;
 if (numberOfSelected == n / 2) {
  if (abs(sum / 2 - currentSum) < *minDiff) {
   *minDiff = abs(sum / 2 - currentSum);
   for (int i = 0; i < n; i++) inSolution[i] = currentItems[i];
  }
 }
 else {
  search(arr, n, currentItems, numberOfSelected, inSolution, minDiff, sum, currentSum, currentPos + 1);
 }
 currentItems[currentPos] = false;
}

void searchPrepare(int* arr, int n) {
 bool* currentItems = new bool[n];
 bool* inSolution = new bool[n];
 int minDiff = INT_MAX;
 int sum = 0;
 for (int i = 0; i < n; i++) {
  sum += arr[i];
  currentItems[i] = inSolution[i] = false;
 }
 search(arr, n, currentItems, 0, inSolution, &minDiff, sum, 0, 0);
 //Вывод решения, может быть убран в отдельный метод или возвращён из функции
 int s1 = 0, s2 = 0;
 cout << "Subste 1: ";
 for (int i = 0; i < n; i++) {
  if (inSolution[i] == true) {
   s1 += arr[i];
   cout << arr[i] << " ";
  }
 }
 cout << endl << "Subset 2: ";
 for (int i = 0; i < n; i++) {
  if (inSolution[i] == false) { 
   s2 += arr[i];
   cout << arr[i] << " ";
  }
 }
 cout << endl << "sum1= " << s1 << ", sum2= " << s2 << ", diff= " << abs(s1-s2);
}

int main() {
 int arr[] = { -5, 3, 1, 2, 4 };
 int n = sizeof(arr) / sizeof(arr[0]);
 searchPrepare(arr, n);
 return 0;
}

07.06.2020, 22:24 [1123 просмотра]