Algoritmos voraces (Greedy Algorithms)
Los algoritmos voraces son un conjunto muy utilizado de métodos que construyen la solución final paso a paso, eligiendo siempre la opción más evidente u óptima en cada etapa. Normalmente, son bastante sencillos de entender, pero a veces puede resultar complicado determinar cuál es la mejor heurística en cada paso.
Desafío
Tienes una mochila (
knapsack) y n elementos. Te gustaría colocar la mayor cantidad posible de artículos, pero sabes que la mochila se romperá si el contenido pesa demasiado (si el peso total sobrepasa el umbral t). Quieres determinar la cantidad máxima de artículos que puedes colocar en la mochila sin que esto resulte un problema.Entrada
La primera línea de la entrada contiene dos números enteros
n (1 ≤ n ≤ ) y t (1 ≤ t ≤ ): representan la cantidad de artículos y el límite máximo que puede soportar la mochila.En la siguiente línea se encuentran
n números enteros separados por espacios, (1 ≤ ≤ ), que son los pesos de cada uno de los artículos.Salida
El programa debe imprimir la cantidad máxima de artículos que puedes transportar.
Ejemplos
Entrada | Salida |
7 10
4 1 2 5 8 7 1 | 4 |
Explicación
Es posible llevar
1, 2, 5, 1, o 4, 1, 2, 1, o 1, 2, 7, 1. En todos estos casos, se incluyen 4 artículos en total.Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB