拔河問題

什麼是拔河問題？

在拔河問題中，給定一組整數，我們的任務是將它們分成兩部分，使得兩個子集的和的差儘可能小。換句話說，將集合分成兩個實力大致相等的組，以參加拔河比賽。當集合大小為偶數時，將其分成兩部分更容易。用奇數個專案這樣做會比較困難。因此，對劃分有一些定義的約束。

如果子集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

列印頁面