Programación dinámica – Mochila 0/1 (Código Python). Dados los pesos y las ganancias de N artÃculos, queremos poner estos artÃculos en una mochila que tenga una capacidad C.
El objetivo es obtener el máximo beneficio de los artÃculos de la mochila. Cada artÃculo solo se puede seleccionar una vez, ya que no tenemos varias cantidades de ningún artÃculo.
- ArtÃculos: [A, B, C, D]
- Pesos: [2, 3, 1, 4]
- Beneficios: [4, 5, 3, 7]
- Capacidad: 5
Probemos alguna combinación cuyo peso total sea menor que la capacidad, 5:
- A + B (peso total: 5) = 9 beneficios
- C + D (peso total: 5) = 10 beneficios
- B + C (peso total: 4) = 8 beneficios
Índice
Solución básica
Programación dinámica de arriba hacia abajo con memorización
Podemos utilizar la memorización para superar los subproblemas superpuestos. Para reiterar, la memorización es cuando almacenamos los resultados de todos los subproblemas previamente resueltos y devolvemos los resultados de la memoria si encontramos un problema que ya ha sido resuelto.
capacity
y currentIndex
) en nuestra función recursiva knapsackRecursive()
, podemos usar una matriz bidimensional para almacenar los resultados de todos los subproblemas resueltos.Como se mencionó anteriormente, necesitamos almacenar los resultados para cada submatriz (es decir, para cada Ãndice posible ‘i’) y para cada capacidad posible ‘c’.
Programación dinámica ascendente
Tratemos de poblar nuestra matriz dp[][]
 de la solución anterior, trabajando de abajo hacia arriba. Esencialmente, queremos encontrar el máximo beneficio para cada subarreglo y para cada capacidad posible.
Esto significa, dp[i][c]
representará el beneficio máximo de mochila para la capacidad ‘c’ calculado a partir de los primeros artÃculos ‘i’.
Partición de igual subconjunto suma – Código de código 416
Este problema sigue el Patrón de mochila 0/1. Una solución básica de fuerza bruta podrÃa ser probar todas las combinaciones de dividir los números dados en dos conjuntos para ver si algún par de conjuntos tiene una suma igual.
Asume si S
representa la suma total de todos los números dados, entonces los dos subconjuntos iguales deben tener una suma igual a S/2
. Esto esencialmente transforma nuestro problema en: «Encuentre un subconjunto de los números dados que tenga una suma total de S/2
«.
Tratemos de poblar nuestro dp[][]
matriz de la solución anterior, trabajando de abajo hacia arriba. Esencialmente, queremos saber si podemos hacer todas las sumas posibles con cada subconjunto.
Esto significa, dp[i][s]
será «verdadero» si podemos sumar ‘s’ a partir de los primeros números ‘i’.
Entonces, para cada número en el Ãndice ‘i’ (0 <= i)
- Excluya el número. En este caso, veremos si podemos obtener ‘s’ del subconjunto excluyendo este número:
dp[i-1][s]
- Incluya el número si su valor no es mayor que ‘s’. En este caso, veremos si podemos encontrar un subconjunto para obtener la suma restante:
dp[i-1][s-num[i]]
Si cualquiera de los dos escenarios anteriores es cierto, podemos encontrar un subconjunto de números con una suma igual a ‘s’.
Suma de subconjunto
Entrada [1, 2, 3, 7]
S = 6
Salida - - Verdadero
Este problema sigue el Patrón de mochila 0/1 y es bastante similar a la partición de suma de subconjuntos iguales.
Una solución básica de fuerza bruta podrÃa ser probar todos los subconjuntos de los números dados para ver si algún conjunto tiene una suma igual a ‘S’.
Intentaremos encontrar si podemos hacer todas las sumas posibles con cada subconjunto para poblar la matriz. dp[TotalNumbers][S+1]
.
Para cada posible suma ‘s’ (donde 0 <= s <= S), tenemos dos opciones:
- Excluya el número. En este caso, veremos si podemos obtener la suma ‘s’ del subconjunto excluyendo este número =>
dp[index-1][s]
- Incluya el número si su valor no es mayor que ‘s’. En este caso, veremos si podemos encontrar un subconjunto para obtener la suma restante =>
dp[index-1][s-num[index]]
Diferencia mÃnima de suma de subconjuntos
Dado un conjunto de números positivos, divida el conjunto en dos subconjuntos con una diferencia mÃnima entre sus sumas de subconjuntos.
Supongamos que S1 y S2 son los dos subconjuntos deseados. Una solución básica de fuerza bruta podrÃa ser intentar agregar cada elemento en S1 o S2, para encontrar la combinación que dé la diferencia de suma mÃnima entre los dos conjuntos.
Usaremos una matriz bidimensional para almacenar los resultados de los subproblemas resueltos. Podemos identificar de forma única un subproblema de 'currentIndex'
y 'Sum1'
; ya que 'Sum2'
siempre será la suma de los números restantes.
Supongamos que ‘S’ representa la suma total de todos los números.
Entonces, lo que estamos tratando de lograr en este problema es encontrar un subconjunto cuya suma sea lo más cercana posible a ‘S / 2’, porque si podemos dividir el conjunto dado en dos subconjuntos de una suma igual, obtenemos la diferencia mÃnima es decir, cero.
Esto transforma nuestro problema en Suma de subconjunto, donde tratamos de encontrar un subconjunto cuya suma sea igual a un número dado – ‘S / 2’ en nuestro caso.
Si no podemos encontrar tal subconjunto, entonces tomaremos el subconjunto que tiene la suma más cercana a ‘S / 2’. Esto es fácilmente posible, ya que calcularemos todas las sumas posibles con cada subconjunto.
Esencialmente, necesitamos calcular todas las sumas posibles hasta ‘S / 2’ para todos los números. Entonces, ¿cómo llenamos la matriz? db[TotalNumbers][S/2+1]
en la moda de abajo hacia arriba.
Para cada posible suma ‘s’ (donde 0 <= s <= S / 2), tenemos dos opciones:
- Excluya el número. En este caso, veremos si podemos obtener la suma ‘s’ del subconjunto excluyendo este
número =>
dp[index-1][s]
- Incluya el número si su valor no es mayor que ‘s’. En este caso, veremos si podemos encontrar un subconjunto para obtener la suma restante =>
dp[index-1][s-num[index]]
Si cualquiera de los dos escenarios anteriores es cierto, podemos encontrar un subconjunto con una suma igual a ‘s’. DeberÃamos profundizar en esto antes de que podamos aprender a encontrar el subconjunto más cercano.
Recuento de la suma del subconjunto
Dado un conjunto de números positivos, encuentre el número total de subconjuntos cuya suma es igual a un número dado ‘S’.
Intentaremos encontrar si podemos hacer todas las sumas posibles con cada subconjunto para poblar la matriz db[TotalNumbers][S+1
].
Entonces, en cada paso tenemos dos opciones:
- Excluya el número. Cuente todos los subconjuntos sin el número dado hasta la suma dada =>
dp[index-1][sum]
- Incluya el número si su valor no es mayor que la «suma». En este caso, contaremos todos los subconjuntos para obtener la suma restante =>
dp[index-1][sum-num[index]]
Para encontrar los conjuntos totales, sumaremos los dos valores anteriores:
dp[index][sum] = dp[index-1][sum] + dp[index-1][sum-num[index]])
Suma objetivo
Leetcode # 494
Dado un conjunto de números positivos (distintos de cero) y una suma objetivo ‘S’. A cada número se le debe asignar un signo ‘+’ o ‘-‘. Necesitamos encontrar formas totales de asignar sÃmbolos para hacer que la suma de números sea igual al objetivo ‘S’.
Se nos pide que encontremos dos subconjuntos de los números dados cuya diferencia sea igual al objetivo ‘S’ dado. Digamos que ‘Suma (s1)’ denota la suma total del conjunto ‘s1’ y ‘Suma (s2)’ denota la suma total del conjunto ‘s2’. Entonces la ecuación requerida es:
Sum(s1) - Sum(s2) = S
Esta ecuación se puede reducir al problema de la suma de subconjuntos. Supongamos que ‘Sum (num)’ denota la suma total de todos los números, por lo tanto:
Sum(s1) + Sum(s2) = Sum(num)
Agreguemos las dos ecuaciones anteriores:
=> Sum(s1) - Sum(s2) + Sum(s1) + Sum(s2) = S + Sum(num) => 2 * Sum(s1) = S + Sum(num) => Sum(s1) = (S + Sum(num)) / 2
Esto esencialmente convierte nuestro problema en: «Encuentra el recuento de subconjuntos de los números dados cuya suma es igual a».
=> (S + Sum(num)) / 2
Gracias por leer este post, espero que te sirva.
Añadir comentario