拔河问题

什么是拔河问题？

在拔河问题中，给定一组整数，我们的任务是将它们分成两部分，使得两个子集的和的差尽可能小。换句话说，将集合分成两个实力大致相等的组，以参加拔河比赛。当集合大小为偶数时，将其分成两部分更容易。用奇数个项目这样做会比较困难。因此，对划分有一些定义的约束。

如果子集N的大小为偶数，可以使用N/2将其分成两部分，但对于奇数N，一个子集的大小必须为(N-1)/2，另一个子集的大小必须为(N+1)/2。

使用回溯法解决拔河问题

假设给定的集合大小为奇数：

Set = {23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4}

当我们分配权重以使差异最小化时，结果子集将是：

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

以下步骤解释了如何使用回溯法来解决拔河问题：

首先创建一个空子集，称为左子集。
用原始集合中所需数量的元素填充这个空子集。所需元素的数量取决于原始集合的大小。如果大小为奇数，则子集应填充 (N-1)/2 个元素；如果大小为偶数，则子集的大小应为 N/2。
检查填充元素的差是否遵循给定的约束条件。如果遵循，则将其标记为解决方案的一部分。
如果差异不是最小值，则尝试其他组合并更新现有解决方案。
一旦第一个子集被填充，其余元素将自动成为第二个子集的一部分。

示例

在下面的示例中，我们将实际演示如何解决拔河问题。

C C++ Java Python

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h>
#include <math.h>
void tgOfWarSoln(int* weight, int n, bool curr[], int select, bool sol[], int *diff, int sum, int total, int pos) {
   //when the pos is covered all weights    
   if (pos == n)     
      return;
    //left elements must be bigger than required result      
   if ((n/2 - select) > (n - pos))   
      return;
   tgOfWarSoln(weight, n, curr, select, sol, diff, sum, total, pos+1);
   select++;
   total += weight[pos];
   //add current element to the solution
   curr[pos] = true;      
   //when solution is formed
   if (select == n/2) {       
      //check whether it is better solution or not
      if (abs(sum/2 - total) < *diff) {     
         *diff = abs(sum/2 - total);
         for (int i = 0; i<n; i++)
            sol[i] = curr[i];
      }
   } else {
      tgOfWarSoln(weight, n, curr, select, sol, diff, sum, total, pos+1);
   }
   //when not properly done, remove current element
   curr[pos] = false;   
}
void checkSolution(int *arr, int n) {
   bool* curr = (bool*)malloc(n*sizeof(bool));
   bool* soln = (bool*)malloc(n*sizeof(bool));
   //set minimum difference to infinity initially
   int diff = INT_MAX;       
   int sum = 0;
   for (int i=0; i<n; i++) {
      //find the sum of all elements
      sum += arr[i];                  
      //make all elements as false
      curr[i] =  soln[i] = false;     
   }
   tgOfWarSoln(arr, n, curr, 0, soln, &diff, sum, 0, 0);
   printf("Left: ");
   for (int i=0; i<n; i++)
      if (soln[i] == true)
         printf("%d ", arr[i]);
   printf("\nRight: ");
   for (int i=0; i<n; i++)
      if (soln[i] == false)
         printf("%d ", arr[i]);
   printf("\n");
   free(curr);
   free(soln);
}
int main() {
   int weight[] = {23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4};
   int n = 11;
   checkSolution(weight, n);
   return 0;
}

#include <iostream>
#include <cmath>
#include <climits>
using namespace std;
void tgOfWarSoln(int* weight, int n, bool curr[], int select, bool sol[], int &diff, int sum, int total, int pos) {
   //when the pos is covered all weights    
   if (pos == n)     
      return;
    //left elements must be bigger than required result      
   if ((n/2 - select) > (n - pos))   
      return;
   tgOfWarSoln(weight, n, curr, select, sol, diff, sum, total, pos+1);
   select++;
   total += weight[pos];
   //add current element to the solution
   curr[pos] = true;      
   //when solution is formed
   if (select == n/2) {       
      //check whether it is better solution or not
      if (abs(sum/2 - total) < diff) {     
         diff = abs(sum/2 - total);
         for (int i = 0; i<n; i++)
            sol[i] = curr[i];
      }
   } else {
      tgOfWarSoln(weight, n, curr, select, sol, diff, sum, total, pos+1);
   }
   //when not properly done, remove current element
   curr[pos] = false;   
}
void checkSolution(int *arr, int n) {
   bool* curr = new bool[n];
   bool* soln = new bool[n];
   //set minimum difference to infinity initially
   int diff = INT_MAX;       
   int sum = 0;
   for (int i=0; i<n; i++) {
      //find the sum of all elements
      sum += arr[i];                  
      //make all elements as false
      curr[i] =  soln[i] = false;     
   }
   tgOfWarSoln(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;
   checkSolution(weight, n);
}

public class Main {
   static void tgOfWarSoln(int[] weight, int n, boolean[] curr, int select, boolean[] sol, int[] diff, int sum, int total, int pos) {
      //when the pos is covered all weights
      if (pos == n)
         return;
      //left elements must be bigger than required result
      if ((n / 2 - select) > (n - pos))
         return;
      tgOfWarSoln(weight, n, curr, select, sol, diff, sum, total, pos + 1);
      select++;
      //add current element to the solution
      total += weight[pos];
      curr[pos] = true;
      //when solution is formed
      if (select == n / 2) {
         //check whether it is better solution or not
         if (Math.abs(sum / 2 - total) < diff[0]) {
            diff[0] = Math.abs(sum / 2 - total);
            for (int i = 0; i < n; i++)
               sol[i] = curr[i];
         }
      } else {
         tgOfWarSoln(weight, n, curr, select, sol, diff, sum, total, pos + 1);
      }
      //when not properly done, remove current element
      curr[pos] = false;
   }
   static void checkSolution(int[] arr, int n) {
      boolean[] curr = new boolean[n];
      boolean[] soln = new boolean[n];
      //set minimum difference to infinity initially
      int[] diff = {Integer.MAX_VALUE};
      int sum = 0;
      for (int i = 0; i < n; i++) {
         //find the sum of all elements
         sum += arr[i];
         //make all elements as false
         curr[i] = soln[i] = false;
      }
      tgOfWarSoln(arr, n, curr, 0, soln, diff, sum, 0, 0);
      System.out.print("Left: ");
      for (int i = 0; i < n; i++)
         if (soln[i] == true)
            System.out.print(arr[i] + " ");
      System.out.println();
      System.out.print("Right: ");
      for (int i = 0; i < n; i++)
         if (soln[i] == false)
            System.out.print(arr[i] + " ");
   }
   public static void main(String[] args) {
      int[] weight = {23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4};
      int n = 11;
      checkSolution(weight, n);
   }
}

def tgOfWarSoln(weight, n, curr, select, sol, diff, sum, total, pos):
    if pos == n:
        return
    
    if (n // 2 - select) > (n - pos):
        return
    
    tgOfWarSoln(weight, n, curr, select, sol, diff, sum, total, pos + 1)
    select += 1
    
    total += weight[pos]
    curr[pos] = True
    
    if select == n // 2:
        if abs(sum // 2 - total) < diff[0]:
            diff[0] = abs(sum // 2 - total)
            for i in range(n):
                sol[i] = curr[i]
    else:
        tgOfWarSoln(weight, n, curr, select, sol, diff, sum, total, pos + 1)
    
    curr[pos] = False

def checkSolution(arr, n):
    curr = [False] * n
    soln = [False] * n
    
    diff = [float('inf')]
    sum = 0
    for i in range(n):
        sum += arr[i]
        curr[i] = soln[i] = False
    
    tgOfWarSoln(arr, n, curr, 0, soln, diff, sum, 0, 0)
    print("Left: ", end="")
    for i in range(n):
        if soln[i] == True:
            print(arr[i], end=" ")
    print()
    print("Right: ", end="")
    for i in range(n):
        if soln[i] == False:
            print(arr[i], end=" ")

weight = [23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4]
n = 11
checkSolution(weight, n)

输出

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

打印页面