Algoritmos Gulosos
Os algoritmos gulosos (greedy algorithms) são um conjunto de abordagens bastante populares que constroem a solução final passo a passo, escolhendo sempre a opção mais evidente ou ótima em cada fase. Normalmente, são métodos simples de compreender, mas por vezes pode ser desafiador determinar qual a melhor heurística em cada etapa.
Desafio
Tem uma mochila e
n itens. Pretende colocar o maior número possível de itens, mas sabe que a mochila se rasgará se o peso total ultrapassar o limite t. Gostaria de saber quantos itens pode colocar na mochila sem que esta fique comprometida.Entrada
A primeira linha da entrada contém dois números inteiros
n (1 ≤ n ≤ ) e t (1 ≤ t ≤ ), que correspondem ao número de itens e ao limite máximo de peso suportado pela mochila.A linha seguinte apresenta
n inteiros separados por espaços, (1 ≤ ≤ ), que são os pesos de cada um dos itens.Saída
O programa deve indicar o número máximo de itens que podem ser transportados.
Exemplos
Entrada | Saída |
7 10
4 1 2 5 8 7 1 | 4 |
Explicação
Podemos levar
1, 2, 5, 1, ou 4, 1, 2, 1, ou 1, 2, 7, 1. Em todos os casos, obtemos 4 itens ao todo.Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB