Considere los pesos y valores de los elementos enumerados a continuación. Tenga en cuenta que solo hay una unidad de cada artículo.
La tarea es elegir un subconjunto de estos elementos de modo que su peso total no supere los 11 kg y su valor total se maximice. Además, ningún artículo puede dividirse. El valor total de los elementos seleccionados por un algoritmo óptimo se denota por V opt . Un algoritmo codicioso clasifica los elementos por su relación valor-peso en orden descendente y los empaqueta con avidez, comenzando por el primer elemento de la lista ordenada. El valor total de los elementos elegidos por el algoritmo codicioso se denota por V codicioso .
El valor de V opt − V codicioso es ______ .
Nota: esta fue una pregunta de tipo numérico.
(A) 16
(B) 8
(C) 44
(D) 60
Respuesta: (A)
Explicación: 
Primero elegiremos item_4 (la proporción de peso de valor es la más alta). El segundo más alto es item_1, pero no se puede elegir debido a su peso. Ahora se recogerá item_3. item_2 no se puede incluir debido a su peso.
Por lo tanto, la ganancia total de V greedy = 20+24 = 44
Por lo tanto, V opt – V codicioso = 60-44 = 16
Entonces, la respuesta es 16.
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