El problema de suma de subconjuntos se define de la siguiente manera. Dado un conjunto de n enteros positivos, S = {a1 ,a2 ,a3 ,…,an} y el entero positivo W, ¿existe un subconjunto de S cuyos elementos suman W? Un programa dinámico para resolver este problema utiliza una array booleana bidimensional X, con n filas y W+1 columnas. X[i, j],1 <= i <= n, 0 <= j <= W, es VERDADERO si y solo si hay un subconjunto de {a1,a2,…,ai} cuyos elementos suman j. ¿Cuál de los siguientes es válido para 2 <= i <= n y ai <= j <= W?
(A) X[i, j] = X[i – 1, j] ∨ X[i, j -ai]
(B) X[i, j] = X[i – 1, j] ∨ X[i – 1, j – ai]
(C) X[i, j] = X[i – 1, j] ∧ X[i, j – ai]
(D) X[i, j] = X[i – 1, j ] ∧ X[i -1, j – ai]
Respuesta: (B)
Explicación:X[I, j] (2 <= i <= n y ai <= j <= W), es verdadero si cualquiera de los siguientes es verdadero
1) La suma de los pesos excluyendo ai es igual a j, es decir, si X[ i-1, j] es verdadera.
2) La suma de los pesos que incluye ai es igual a j, es decir, si X[i-1, j-ai] es cierto, obtenemos (j – ai) + ai como j
Consulte https://www.geeksforgeeks.org/dynamic-programming-subset-sum-problem/ para obtener más información.
Cuestionario de esta pregunta
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA