Una variación del problema de la mochila: cómo resolver el problema de la suma de subconjuntos iguales de particiones en Java

Anteriormente, escribí sobre cómo resolver el problema de la mochila (KP) con programación dinámica. Usted puede leer sobre ello aquí.

Hoy quiero discutir una variación de KP: el problema de la suma de subconjuntos iguales de particiones. Vi este problema por primera vez en Leetcode; esto fue lo que me impulsó a aprender y escribir sobre KP.

Este es el enunciado del problema (reproducido parcialmente sin ejemplos):

Dada una matriz no vacía que contiene solo enteros positivos, encuentre si la matriz se puede dividir en dos subconjuntos de manera que la suma de elementos en ambos subconjuntos sea igual.

Para ver el enunciado completo del problema, con restricciones y ejemplos, consulte el problema de Leetcode.

Programación dinámica

Al igual que con KP, resolveremos esto usando programación dinámica. Dado que se trata de una variación de KP, la lógica y la metodología son muy similares.

Solución

Alojaremos nuestra solución en un método que devuelva un valor booleano: verdadero si la matriz se puede dividir en subconjuntos iguales y falso en caso contrario.

Paso 1: protegerse contra la suma de matriz impar

Trivialmente, si todos los números en la matriz suman una suma impar, podemos devolver falso. Solo procedemos si la matriz se suma a una suma par.

Paso 2: crear la tabla

A continuación, creamos la tabla.

Las filas de la tabla representan el conjunto de elementos de la matriz a considerar, mientras que las columnas de la tabla indican la suma a la que queremos llegar. Los valores de la tabla son simplemente valores booleanos, que indican si se puede llegar a una suma (columna) con un conjunto de elementos de matriz (fila).

Concretamente, la fila i representa un conjunto de elementos de matriz de índices 0 a ( i -1). La razón de este desplazamiento de 1 es que la fila 0 representa un conjunto vacío de elementos. Por lo tanto, la fila 1 representa el primer elemento de la matriz (índice 0), la fila 2 representa los dos primeros elementos de la matriz (índices 0–1) y así sucesivamente. En total, creamos n + 1filas, incluido 0.

Solo queremos saber si podemos sumar exactamente la mitad de la suma total de la matriz. Entonces solo necesitamos crear totalSum / 2 + 1columnas, incluido 0.

Paso 3: prellenado de la mesa

Podemos comenzar a completar inmediatamente las entradas para los casos base en nuestra tabla: fila 0 y columna 0.

En la primera fila, todas las entradas, excepto la primera, deben estar false. Recuerde que la primera fila representa un conjunto vacío. Naturalmente, no podemos llegar a ninguna suma objetivo (número de columna) excepto 0.

En la primera columna, todas las entradas deben ser true. Siempre podemos, trivialmente, llegar a una suma objetivo de 0, independientemente del conjunto de elementos con los que tengamos que trabajar.

Paso 4: Construyendo la mesa (el quid del problema)

Alguna entrada en la tabla en la fila i y la columna j es true(alcanzable) si se cumple una de las siguientes tres condiciones:

  1. la entrada en la fila i -1 y la columna j es true. Recuerde lo que representa el número de fila. Por lo tanto, si podemos lograr una suma particular con un subconjunto de los elementos que tenemos actualmente, también podemos lograr esa suma con nuestro conjunto actual de elementos, simplemente sin usar los elementos adicionales. Esto es trivial. Llamemos a esto prevRowIsTrue.
  2. El elemento actual es exactamente la suma que queremos alcanzar. Esto también es trivialmente cierto. Llamemos a esto isExactMatch.
  3. Si no se cumplen las dos condiciones anteriores, nos queda una forma restante de alcanzar nuestra suma objetivo. Aquí, usamos el elemento actual, el elemento adicional en el conjunto de elementos de nuestra fila actual en comparación con el conjunto de elementos de la fila anterior, y verificamos que podemos alcanzar el resto de la suma objetivo. Llamemos a esto canArriveAtSum.

Desempaquetamos la condición 3. Solo podemos usar el elemento actual si es menor que nuestra suma objetivo. Si son iguales, la condición 2 se cumpliría. Si es más grande, no podemos usarlo. Por lo tanto, el primer paso es asegurarse de que el elemento actual <suma objetivo.

Después de usar nuestro elemento actual, nos queda el resto de nuestra suma objetivo. Luego, verificamos si eso es posible al verificar la entrada correspondiente en la fila anterior.

Al igual que con el KP regular, queremos construir progresivamente nuestra tabla de abajo hacia arriba. Comenzamos con los casos base, hasta llegar a nuestra solución final.

Paso 5: Devolver la respuesta

Simplemente regresamos return mat[nums.length][totalSum / 2].

Código de trabajo

¡Gracias por leer!