给定一组n个整数，将该集合划分为两个大小为n/2的子集，使两个子集之和的差尽可能小。如果n为偶数，则两个子集的大小必须严格为n/2，如果n为奇数，则一个子集的大小必须为（n-1）/2，而另一个子集的大小必须为（n+1）/2。 例如，假设给定的集合是{3,4,5，-3,100,1,89,54,23,20}，集合的大小是10。这个集合的输出应该是{4,100,1,23,20}和{3,5，-3,89,54}。两个输出子集的大小均为5，且两个子集中的元素之和相同（148和148）。 让我们考虑另一个例子，其中n是奇数。设给定集为{23,45，-34,12,0,98，-99,4,189，-1,4}。输出子集应该是{45、-34、12、98、-1}和{23、0、-99、4、189、4}。两个子集中的元素之和分别为120和121。 下面的解决方案尝试了一半大小的所有可能子集。如果形成了一半大小的一个子集，其余的元素形成了另一个子集。我们将当前集合初始化为空，然后逐个构建它。每个元素都有两种可能，要么是当前集合的一部分，要么是剩余元素（其他子集）的一部分。我们考虑两种可能性的每一个元素。当当前集合的大小变为n/2时，我们将检查此解决方案是否优于迄今为止可用的最佳解决方案。如果是，那么我们将更新最佳解决方案。 以下是拔河问题的实施。它打印所需的数组。
null
C++
#include <bits/stdc++.h> using namespace std; // function that tries every possible solution by calling itself recursively void TOWUtil( int * arr, int n, bool * curr_elements, int no_of_selected_elements, bool * soln, int * min_diff, int sum, int curr_sum, int curr_position) { // checks whether the it is going out of bound if (curr_position == n) return ; // checks that the numbers of elements left are not less than the // number of elements required to form the solution if ((n/2 - no_of_selected_elements) > (n - curr_position)) return ; // consider the cases when current element is not included in the solution TOWUtil(arr, n, curr_elements, no_of_selected_elements, soln, min_diff, sum, curr_sum, curr_position+1); // add the current element to the solution no_of_selected_elements++; curr_sum = curr_sum + arr[curr_position]; curr_elements[curr_position] = true ; // checks if a solution is formed if (no_of_selected_elements == n/2) { // checks if the solution formed is better than the best solution so far if ( abs (sum/2 - curr_sum) < *min_diff) { *min_diff = abs (sum/2 - curr_sum); for ( int i = 0; i<n; i++) soln[i] = curr_elements[i]; } } else { // consider the cases where current element is included in the solution TOWUtil(arr, n, curr_elements, no_of_selected_elements, soln, min_diff, sum, curr_sum, curr_position+1); } // removes current element before returning to the caller of this function curr_elements[curr_position] = false ; } // main function that generate an arr void tugOfWar( int *arr, int n) { // the boolean array that contains the inclusion and exclusion of an element // in current set. The number excluded automatically form the other set bool * curr_elements = new bool [n]; // The inclusion/exclusion array for final solution bool * soln = new bool [n]; int min_diff = INT_MAX; int sum = 0; for ( int i=0; i<n; i++) { sum += arr[i]; curr_elements[i] = soln[i] = false ; } // Find the solution using recursive function TOWUtil() TOWUtil(arr, n, curr_elements, 0, soln, &min_diff, sum, 0, 0); // Print the solution cout << "The first subset is: " ; for ( int i=0; i<n; i++) { if (soln[i] == true ) cout << arr[i] << " " ; } cout << "The second subset is: " ; for ( int i=0; i<n; i++) { if (soln[i] == false ) cout << arr[i] << " " ; } } // Driver program to test above functions int main() { int arr[] = {23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4}; int n = sizeof (arr)/ sizeof (arr[0]); tugOfWar(arr, n); return 0; } |
JAVA
// Java program for Tug of war import java.util.*; import java.lang.*; import java.io.*; class TugOfWar { public int min_diff; // function that tries every possible solution // by calling itself recursively void TOWUtil( int arr[], int n, boolean curr_elements[], int no_of_selected_elements, boolean soln[], int sum, int curr_sum, int curr_position) { // checks whether the it is going out of bound if (curr_position == n) return ; // checks that the numbers of elements left // are not less than the number of elements // required to form the solution if ((n / 2 - no_of_selected_elements) > (n - curr_position)) return ; // consider the cases when current element // is not included in the solution TOWUtil(arr, n, curr_elements, no_of_selected_elements, soln, sum, curr_sum, curr_position+ 1 ); // add the current element to the solution no_of_selected_elements++; curr_sum = curr_sum + arr[curr_position]; curr_elements[curr_position] = true ; // checks if a solution is formed if (no_of_selected_elements == n / 2 ) { // checks if the solution formed is // better than the best solution so // far if (Math.abs(sum / 2 - curr_sum) < min_diff) { min_diff = Math.abs(sum / 2 - curr_sum); for ( int i = 0 ; i < n; i++) soln[i] = curr_elements[i]; } } else { // consider the cases where current // element is included in the // solution TOWUtil(arr, n, curr_elements, no_of_selected_elements, soln, sum, curr_sum, curr_position + 1 ); } // removes current element before // returning to the caller of this // function curr_elements[curr_position] = false ; } // main function that generate an arr void tugOfWar( int arr[]) { int n = arr.length; // the boolean array that contains the // inclusion and exclusion of an element // in current set. The number excluded // automatically form the other set boolean [] curr_elements = new boolean [n]; // The inclusion/exclusion array for // final solution boolean [] soln = new boolean [n]; min_diff = Integer.MAX_VALUE; int sum = 0 ; for ( int i = 0 ; i < n; i++) { sum += arr[i]; curr_elements[i] = soln[i] = false ; } // Find the solution using recursive // function TOWUtil() TOWUtil(arr, n, curr_elements, 0 , soln, sum, 0 , 0 ); // Print the solution System.out.print( "The first subset is: " ); for ( int i = 0 ; i < n; i++) { if (soln[i] == true ) System.out.print(arr[i] + " " ); } System.out.print( "The second subset is: " ); for ( int i = 0 ; i < n; i++) { if (soln[i] == false ) System.out.print(arr[i] + " " ); } } // Driver program to test above functions public static void main (String[] args) { int arr[] = { 23 , 45 , - 34 , 12 , 0 , 98 , - 99 , 4 , 189 , - 1 , 4 }; TugOfWar a = new TugOfWar(); a.tugOfWar(arr); } } // This code is contributed by Chhavi |
Python3
# Python3 program for above approach # function that tries every possible # solution by calling itself recursively def TOWUtil(arr, n, curr_elements, no_of_selected_elements, soln, min_diff, Sum , curr_sum, curr_position): # checks whether the it is going # out of bound if (curr_position = = n): return # checks that the numbers of elements # left are not less than the number of # elements required to form the solution if (( int (n / 2 ) - no_of_selected_elements) > (n - curr_position)): return # consider the cases when current element # is not included in the solution TOWUtil(arr, n, curr_elements, no_of_selected_elements, soln, min_diff, Sum , curr_sum, curr_position + 1 ) # add the current element to the solution no_of_selected_elements + = 1 curr_sum = curr_sum + arr[curr_position] curr_elements[curr_position] = True # checks if a solution is formed if (no_of_selected_elements = = int (n / 2 )): # checks if the solution formed is better # than the best solution so far if ( abs ( int ( Sum / 2 ) - curr_sum) < min_diff[ 0 ]): min_diff[ 0 ] = abs ( int ( Sum / 2 ) - curr_sum) for i in range (n): soln[i] = curr_elements[i] else : # consider the cases where current # element is included in the solution TOWUtil(arr, n, curr_elements, no_of_selected_elements, soln, min_diff, Sum , curr_sum, curr_position + 1 ) # removes current element before returning # to the caller of this function curr_elements[curr_position] = False # main function that generate an arr def tugOfWar(arr, n): # the boolean array that contains the # inclusion and exclusion of an element # in current set. The number excluded # automatically form the other set curr_elements = [ None ] * n # The inclusion/exclusion array # for final solution soln = [ None ] * n min_diff = [ 999999999999 ] Sum = 0 for i in range (n): Sum + = arr[i] curr_elements[i] = soln[i] = False # Find the solution using recursive # function TOWUtil() TOWUtil(arr, n, curr_elements, 0 , soln, min_diff, Sum , 0 , 0 ) # Print the solution print ( "The first subset is: " ) for i in range (n): if (soln[i] = = True ): print (arr[i], end = " " ) print () print ( "The second subset is: " ) for i in range (n): if (soln[i] = = False ): print (arr[i], end = " " ) # Driver Code if __name__ = = '__main__' : arr = [ 23 , 45 , - 34 , 12 , 0 , 98 , - 99 , 4 , 189 , - 1 , 4 ] n = len (arr) tugOfWar(arr, n) # This code is contributed by PranchalK |
C#
// C# program for Tug of war using System; class GFG { public int min_diff; // function that tries every possible solution // by calling itself recursively void TOWUtil( int []arr, int n, Boolean []curr_elements, int no_of_selected_elements, Boolean []soln, int sum, int curr_sum, int curr_position) { // checks whether the it is going out of bound if (curr_position == n) return ; // checks that the numbers of elements left // are not less than the number of elements // required to form the solution if ((n / 2 - no_of_selected_elements) > (n - curr_position)) return ; // consider the cases when current element // is not included in the solution TOWUtil(arr, n, curr_elements, no_of_selected_elements, soln, sum, curr_sum, curr_position + 1); // add the current element to the solution no_of_selected_elements++; curr_sum = curr_sum + arr[curr_position]; curr_elements[curr_position] = true ; // checks if a solution is formed if (no_of_selected_elements == n / 2) { // checks if the solution formed is // better than the best solution so // far if (Math.Abs(sum / 2 - curr_sum) < min_diff) { min_diff = Math.Abs(sum / 2 - curr_sum); for ( int i = 0; i < n; i++) soln[i] = curr_elements[i]; } } else { // consider the cases where current // element is included in the // solution TOWUtil(arr, n, curr_elements, no_of_selected_elements, soln, sum, curr_sum, curr_position + 1); } // removes current element before // returning to the caller of this // function curr_elements[curr_position] = false ; } // main function that generate an arr void tugOfWar( int []arr) { int n = arr.Length; // the boolean array that contains the // inclusion and exclusion of an element // in current set. The number excluded // automatically form the other set Boolean[] curr_elements = new Boolean[n]; // The inclusion/exclusion array for // final solution Boolean[] soln = new Boolean[n]; min_diff = int .MaxValue; int sum = 0; for ( int i = 0; i < n; i++) { sum += arr[i]; curr_elements[i] = soln[i] = false ; } // Find the solution using recursive // function TOWUtil() TOWUtil(arr, n, curr_elements, 0, soln, sum, 0, 0); // Print the solution Console.Write( "The first subset is: " ); for ( int i = 0; i < n; i++) { if (soln[i] == true ) Console.Write(arr[i] + " " ); } Console.Write( "The second subset is: " ); for ( int i = 0; i < n; i++) { if (soln[i] == false ) Console.Write(arr[i] + " " ); } } // Driver Code public static void Main (String[] args) { int []arr = {23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4}; GFG a = new GFG(); a.tugOfWar(arr); } } // This code is contributed by 29AjayKumar |
PHP
<?php // PHP program for above approach // Function that tries every possible // solution by calling itself recursively function TOWUtil(& $arr , $n , & $curr_elements , $no_of_selected_elements , & $soln , & $min_diff , $sum , $curr_sum , $curr_position ) { // checks whether the it is going // out of bound if ( $curr_position == $n ) return ; // checks that the numbers of elements left // are not less than the number of elements // required to form the solution if (( intval ( $n / 2) - $no_of_selected_elements ) > ( $n - $curr_position )) return ; // consider the cases when current element // is not included in the solution TOWUtil( $arr , $n , $curr_elements , $no_of_selected_elements , $soln , $min_diff , $sum , $curr_sum , $curr_position + 1); // add the current element to the solution $no_of_selected_elements ++; $curr_sum = ( $curr_sum + $arr [ $curr_position ]); $curr_elements [ $curr_position ] = true; // checks if a solution is formed if ( $no_of_selected_elements == intval ( $n / 2)) { // checks if the solution formed is // better than the best solution so far if ( abs ( intval ( $sum / 2) - $curr_sum ) < $min_diff ) { $min_diff = abs ( intval ( $sum / 2) - $curr_sum ); for ( $i = 0; $i < $n ; $i ++) $soln [ $i ] = $curr_elements [ $i ]; } } else { // consider the cases where current // element is included in the solution TOWUtil( $arr , $n , $curr_elements , $no_of_selected_elements , $soln , $min_diff , $sum , $curr_sum , $curr_position + 1); } // removes current element before // returning to the caller of this function $curr_elements [ $curr_position ] = false; } // main function that generate an arr function tugOfWar(& $arr , $n ) { // the boolean array that contains the // inclusion and exclusion of an element // in current set. The number excluded // automatically form the other set $curr_elements = array_fill (0, $n , 0); // The inclusion/exclusion array // for final solution $soln = array_fill (0, $n , 0); $min_diff = PHP_INT_MAX; $sum = 0; for ( $i = 0; $i < $n ; $i ++) { $sum += $arr [ $i ]; $curr_elements [ $i ] = $soln [ $i ] = false; } // Find the solution using recursive // function TOWUtil() TOWUtil( $arr , $n , $curr_elements , 0, $soln , $min_diff , $sum , 0, 0); // Print the solution echo "The first subset is: " ; for ( $i = 0; $i < $n ; $i ++) { if ( $soln [ $i ] == true) echo $arr [ $i ] . " " ; } echo "The second subset is: " ; for ( $i = 0; $i < $n ; $i ++) { if ( $soln [ $i ] == false) echo $arr [ $i ] . " " ; } } // Driver Code $arr = array (23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4); $n = count ( $arr ); tugOfWar( $arr , $n ); // This code is contributed // by rathbhupendra ?> |
Javascript
<script> // javascript program for Tug of war var min_diff; // function that tries every possible solution // by calling itself recursively function TOWUtil(arr , n, curr_elements , no_of_selected_elements, soln , sum, curr_sum , curr_position) { // checks whether the it is going out of bound if (curr_position == n) return ; // checks that the numbers of elements left // are not less than the number of elements // required to form the solution if ((parseInt(n / 2) - no_of_selected_elements) > (n - curr_position)) return ; // consider the cases when current element // is not included in the solution TOWUtil(arr, n, curr_elements, no_of_selected_elements, soln, sum, curr_sum, curr_position + 1); // add the current element to the solution no_of_selected_elements++; curr_sum = curr_sum + arr[curr_position]; curr_elements[curr_position] = true ; // checks if a solution is formed if (no_of_selected_elements == parseInt(n / 2)) { // checks if the solution formed is // better than the best solution so // far if (Math.abs(parseInt(sum / 2) - curr_sum) < min_diff) { min_diff = Math.abs(parseInt(sum / 2) - curr_sum); for (i = 0; i < n; i++) soln[i] = curr_elements[i]; } } else { // consider the cases where current // element is included in the // solution TOWUtil(arr, n, curr_elements, no_of_selected_elements, soln, sum, curr_sum, curr_position + 1); } // removes current element before // returning to the caller of this // function curr_elements[curr_position] = false ; } // main function that generate an arr function tugOfWar(arr) { var n = arr.length; // the boolean array that contains the // inclusion and exclusion of an element // in current set. The number excluded // automatically form the other set var curr_elements = Array(n).fill( true ); // The inclusion/exclusion array for // final solution var soln = Array(n).fill( false ); min_diff = Number.MAX_VALUE; var sum = 0; for ( var i = 0; i < n; i++) { sum += arr[i]; curr_elements[i] = soln[i] = false ; } // Find the solution using recursive // function TOWUtil() TOWUtil(arr, n, curr_elements, 0, soln, sum, 0, 0); // Print the solution document.write( "The first subset is: " ); for ( var i = 0; i < n; i++) { if (soln[i] == true ) document.write(arr[i] + " " ); } document.write( "<br/>The second subset is: " ); for ( var i = 0; i < n; i++) { if (soln[i] == false ) document.write(arr[i] + " " ); } } // Driver program to test above functions var arr = [ 23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4 ]; tugOfWar(arr); // This code is contributed by Rajput-Ji </script> |
输出：
The first subset is: 45 -34 12 98 -1The second subset is: 23 0 -99 4 189 4
时间复杂性： O（2^n） 本文由 阿什阿南德 并由Geeksforgeks团队审核。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
