Suma de Subconjuntos por DP

Contexto:

El problema de la suma de subconjuntos consiste en dado un arreglo A con n números enteros positivos, y dado un entero positivo k, se quiere determinar si existe un subconjunto de A cuya suma sea igual a k.

Si se trata de resolver este problema con fuerza bruta, su solución puede ser muy costosa (con una cota de complejidad exponencial), por esta razón se han ideado nuevas formas de resolverlo sin sacrificar tantos recursos, una de estas formas es la solución aplicando Programación Dinámica en Bottom-Up la cual crea un arreglo bidimensional con el que se empezarán a almacenar estados y a partir de dichos estados se calculan nuevos de éstos hasta rellenar la tabla.

¿Qué es esta demostración?

Es una demostración interactiva para explicar la solución al problema de suma de subconjuntos mediante programación dinámica de una forma amigable para que el usuario pueda comprender cómo es que opera dicha solución.

En esta animación hacemos una analogía para el arreglo y para la suma objetivo, donde en vez de tener almacenados números en un arreglo, tenemos un contenedor con cubos de agua de distinta capacidad; y en vez de tener un número como objetivo, tenemos una cantidad de árboles que queremos hacer crecer. Entonces nos preguntaremos si en nuestro contenedor con varios cubos de agua tenemos algún conjunto cuya suma de litros de agua sea la exacta para hacer crecer a nuestra cantidad de árboles deseada.