Programa que divida un conjunto en dos subconjuntos que sumen lo mismo.

Un programa en c, c++ o python que reciba un conjunto de 10 números enteros aleatorios, lo divida en dos subconjuntos de igual cantidad de números (5 y 5) y que la suma de los números en cada subconjunto sea lo más parecida posible.

Ejemplo:

Teniendo el conjunto (0, 1, 2, 3, 4, 5, 6, 7, 8, 9) 

Deberemos obtener los siguientes subconjuntos:

1.- (0, 9, 2, 7, 4) la suma da como resultado 22

2.- (1, 8, 3, 6, 5) la suma da como resultado 23

Esta lo más balanceado posible.

Nota: El conjunto no siempre estará ordenado por lo que será necesario incluir un algoritmo de ordenamiento, pero de eso me encargo yo. Mientras el código balancee correctamente cualquier conjunto me basta y sobra.

Respuesta
1

No voy a resolver tu problema, porque no conozco la solución y, por lo que he visto en https://www.it-swarm-es.com/es/arrays/como-dividir-un-conjunto-en-dos-subconjuntos-de-tal-manera-que-la-diferencia-entre-la-suma-de-numeros-en-dos-conjuntos-sea-minima/972300976/ no parece sencilla. Además el problema que planteas difiere del que se plantea ahí en que el número de elementos (cardinal) de cada subconjunto es fijo (en este caso 5). Se me ocurre que se puede hacer la suma de todos los números del conjunto original, dividirla por dos (redondeando a la baja, llamémosla S) e ir cogiendo las sumas de todas las combinaciones de los 10 elementos tomados de 5 en 5 (252 combinaciones). Anotamos en una tabla los índices de los cinco elementos y su suma. Luego ordenamos la tabla y buscamos en ella el valor más cercano a S. Ese nos dará los índices de uno de los subconjuntos y los restantes el otro.

Es solo una idea. No lo he probado ni sé lo suficiente de esos lenguajes de programación para programar el algoritmo, aunque creo que voy a intentarlo en C++ cuando tenga un rato.

Como con lo que estoy más familiarizado últimamente es con la "programación" batch, he preparado un BAT solo para tu ejemplo:

@echo off
Setlocal EnableDelayedExpansion
set cont=0
for /l %%i in (0, 1, 9) do (
   set /a ip1=%%i + 1
   for /l %%j in (!ip1!, 1, 9) do (
      set /a jp1=%%j + 1
      for /l %%k in (!jp1!, 1, 9) do (
         set /a kp1=%%k + 1
         for /l %%l in (!kp1!, 1, 9) do (
            set /a lp1=%%l + 1
            for /l %%m in (!lp1!, 1, 9) do (
               set /a cont+=1
               set /a suma=%%i + %%j + %%k + %%l + %%m
               Echo ! Cont! %%i%%j%%k%%l%%M ! Suma!
               )
            )
         )
      )
   )

Partiendo de que, en este ejemplo, S=22, me salen bastantes soluciones. Pongo las cinco primeras:
01489/23567
01579/23468
01678/23459
02389/14567
02479/13568
Por supuesto que el BAT solo sirve para este ejemplo, que la revisión de las sumas las he hecho visualmente y que habría que incluir tratamientos tipo array y un aleatorizador, pero es solo para ver que el algoritmo creo que tiene posibilidades.

El editor de la página ha cambiado algunas cosas en el BAT que harán que funcione mal, en particular ha separado la "!" inicial de CONT y SUMA. Debe estar "pegada" como las de IP1, JP1, KP1 y LP1.

También ha puesto %%M en el ECHO en vez de %%m, pero eso tal vez no importa.

Calificación". He seguido en batch y este sería el "programa" algo más depurado:

@echo off
Setlocal EnableDelayedExpansion
set /a i=0
:bucle
if "%1"=="" goto :fincarga
set c%i%=%1
set /a i+=1
shift
goto :bucle
:fincarga
set semisuma=0
if not "%i%"=="10" echo Hay que pasar 10 valores&goto :eof
set /a i-=1
for /l %%n in (0,1,%i%) do set /a semisuma+=!c%%n!
set /a semisuma=%semisuma%/2
set /a difg=%semisuma%
set /a suma=0
for /l %%i in (0, 1, 9) do (
   set /a ip1=%%i + 1
   for /l %%j in (!ip1!, 1, 9) do (
      set /a jp1=%%j + 1
      for /l %%k in (!jp1!, 1, 9) do (
         set /a kp1=%%k + 1
         for /l %%l in (!kp1!, 1, 9) do (
            set /a lp1=%%l + 1
            for /l %%m in (!lp1!, 1, 9) do (
               set /a suma=!c%%i! + !c%%j! + !c%%k! + !c%%l! + !c%%m!
               set /a dif=%semisuma% - !suma!
               if "!dif!" leq "!difg!" set /a difg=!dif!&set ig=%%i&set jg=%%j&set kg=%%k&set lg=%%l&set mg=%%m
               )
            )
         )
      )
   )
Echo resultado: %ig%%jg%%kg%%lg%%mg% !c%ig%!/!c%jg%!/!c%kg%!/!c%lg%!/!c%mg%!

Habría que salvarlo, por ejemplo como PartConj.bat, e invocarlo desde una ventana CMD situada en la carpeta donde se haya salvado de esta manera:

PartConj 23 45 200 324 87 6 9 234 45 10

(Con los diez valores "aleatorios" sobre los que se quiere trabajar). Para este ejemplo el resultado sería:

resultado: 12489 45/200/87/45/10

Es decir que uno de los conjuntos sería {45, 200, 87, 45, 10} de suma 387 y el otro {23, 324, 6, 9, 234} de suma 596, que parece ser lo más balanceado que se puede en este caso.

Con este bat se generarían los 10 números aleatorios (entre 0 y 500) antes de invocar al bat anterior:

@echo off
Setlocal EnableDelayedExpansion
set /a max=500
set /a min=0
set /a ncar=10
set cadena=
for /l %%i in (1,1,%ncar%) do set /a n=!RANDOM!*%max%/32768+%min%&set cadena=!cadena! !n!
echo %ncar% n£meros aleatorios entre %min% y %max% !cadena!
call PartConj !cadena!

Este es un ejemplo de uso:

10 números aleatorios entre 0 y 500 78 61 135 137 329 315 463 66 265 462
Resultado: 13479 61/137/329/66/462

Aunque el generador de números aleatorios podría sacar cualquier cantidad de números, sin más que modificar la variable NCAR, el PartConj.bat solo permite tratar conjuntos de 10 (para que tratara otros conjuntos de otras cantidades de números habría que modificar el número de bucles FOR)

Añade tu respuesta

Haz clic para o

Más respuestas relacionadas