Dado un conjunto de n enteros, se divide el conjunto en dos subconjuntos de n/2 tamaños cada uno de manera que la diferencia de la suma de los dos subconjuntos sea la mínima posible. Si n es par, entonces los tamaños de dos subconjuntos deben ser estrictamente n/2 y si n es impar, entonces el tamaño de un subconjunto debe ser (n-1)/2 y el tamaño del otro subconjunto debe ser (n+1)/2 .
Por ejemplo, si el conjunto dado es {3, 4, 5, -3, 100, 1, 89, 54, 23, 20}, el tamaño del conjunto es 10. La salida para este conjunto debe ser {4, 100, 1, 23, 20} y {3, 5, -3, 89, 54}. Ambos subconjuntos de salida son de tamaño 5 y la suma de elementos en ambos subconjuntos es la misma (148 y 148).
Consideremos otro ejemplo donde n es impar. Sea el conjunto dado {23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4}. Los subconjuntos de salida deben ser {45, -34, 12, 98, -1} y {23, 0, -99, 4, 189, 4}. Las sumas de elementos en dos subconjuntos son 120 y 121 respectivamente.
La siguiente solución prueba todos los subconjuntos posibles de la mitad del tamaño. Si se forma un subconjunto de la mitad del tamaño, los elementos restantes forman el otro subconjunto. Inicializamos el conjunto actual como vacío y lo construimos uno por uno. Hay dos posibilidades para cada elemento, o es parte del conjunto actual o es parte de los elementos restantes (otro subconjunto). Consideramos ambas posibilidades para cada elemento. Cuando el tamaño del conjunto actual se vuelve n/2, verificamos si esta solución es mejor que la mejor solución disponible hasta el momento. Si es así, actualizamos la mejor solución.
A continuación se muestra la implementación del problema de tira y afloja. Imprime las arrays requeridas.
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 << "\nThe 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("\nThe 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("\nThe 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 "\nThe 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>
Producción:
The first subset is: 45 -34 12 98 -1 The second subset is: 23 0 -99 4 189 4
Complejidad de tiempo: O(2^n)
Este artículo fue compilado por Ashish Anand y revisado por el equipo de GeeksforGeeks. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA