Llevo varios días luchando con este problema, quizás porque lo estoy enfocando de forma equivocada. ¡Espero que alguien pueda ayudarme a ver la luz!
PROBLEMA
Considera que hay cuatro tazas de peniques. Cada taza tiene una cantidad aleatoria de peniques.
Necesito determinar cómo dividir las tazas en dos grupos, dos tazas en cada grupo, de manera que el total de peniques en un grupo menos el total de peniques en el segundo grupo sea un mínimo, e idealmente cero.
Es muy sencillo resolver este problema si supiera la cantidad de peniques que hay en cada vaso. Así que quiero utilizar el álgebra lineal para ayudarme a determinar esas cantidades. Una vez que tenga las cantidades, puedo hacer sumas de prueba en un ordenador rápido para encontrar una división óptima de las tazas.
Planteo el problema en el contexto de cuatro copas. Pero la aplicación práctica que estoy tratando de resolver podría tener 32 tazas, por lo que el número de combinaciones que habría que probar es $\binom{32}{16}$ que son más de 60 millones. Hacerlo manualmente nos llevaría una eternidad.
ENFOQUE MATEMÁTICO
Supongamos que $A$ es un vector que representa el número desconocido de peniques en cada taza, $B$ es una multitud de vectores que asignan cada taza a un grupo, y $C$ es la diferencia de peniques totales entre los grupos de vasos.
$$A=C\cdot B^{-1}$$
Aunque creo que tengo el problema configurado correctamente, el determinante de $B$ es siempre cero dados los requisitos de $B$ . Así que no puedo determinar el número de centavos en cada taza.
Condiciones;
$$n\in\{2\cdot\mathbb{Z}\}\mid n\geqslant2\ $$
$$A=[\left|a_1\right|... \left|a_n\right|]$$
$$C=\begin{bmatrix} c_{1}\\ \vdots \\ c_{n}\\ \end{bmatrix}$$
$$B=\begin{bmatrix} B_{x}\\ B_{y}\\ \end{bmatrix}$$
$$B_x=\begin{bmatrix} b_{1,1} \dots b_{n,1} \\ \vdots \\ b_{1,\frac{n}{2}} \dots b_{n,\frac{n}{2}} \\ \end{bmatrix}$$
$$B_{y}=-B_x$$
con la limitación adicional de que todos los términos en $B_x$ se les asigna arbitrariamente +1 o -1, y cada vector columna en $B_x$ es único.
Al asignar $B_y$ = - $B_x$ cada columna de $B$ tiene garantizado un conjunto de $\frac{n}{2}$ términos = 1 y otro conjunto de igual tamaño de $\frac{n}{2}$ términos = -1.
Dado que todos los términos de $A$ son positivos, los vectores columna equilibrados de $B$ separa efectivamente el $A$ vector en dos vectores de igual longitud; un grupo de vectores positivos y un grupo de vectores negativos. El objetivo final es encontrar un vector columna, no necesariamente en $B$ que crea una suma mínima de todos los términos en $A$ . Pero si el determinante de $B$ es siempre cero, no veo cómo resolver mi problema. ¿Estoy cometiendo un error o hay una forma mejor de enfocar el problema?
¿Alguna idea?
