El peso de una secuencia a 0 , a 1 , …, a n-1 de números reales se define como a 0 +a 1 /2+…+ a a-1 /2 n-1 . Una subsecuencia de una secuencia se obtiene eliminando algunos elementos de la secuencia, manteniendo el mismo orden de los elementos restantes. Sea X el peso máximo posible de una subsecuencia de a 0 , a 1 , …,a n-1 e Y el peso máximo posible de una subsecuencia de a 1 , a 2 , …,a n-1 . Entonces X es igual a
(A) max(Y, a0+Y)
(B) max(Y, a0+Y/2)
(C)max(Y, a0+2Y)
(D) a0+Y/2
Respuesta: (B)
Explicación: Usando conceptos de Programación Dinámica, para encontrar el peso máximo posible de una subsecuencia de X, tendremos dos alternativas:
1. Hacer no incluir a0 en la subsecuencia: entonces el peso máximo posible será igual al peso máximo posible de una subsecuencia de {a1, a2,….an} que está representada por Y
2. Incluir a0: entonces el peso máximo posible será igual a a0 + (cada número elegido en Y se dividirá por 2) a0 + Y/2. Aquí puede notar que Y mismo elegirá la subsecuencia óptima para maximizar el peso.
La respuesta final será Max(Case1, Case2), es decir, Max(Y, a0 + Y/2). Por lo tanto B).
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