Greedy Algorithms
Greedy algorithms are a popular set of approaches that build the final solution piece-by-piece always choosing the most obvious/optimal solution at each stage. They are usually pretty straightforward but sometimes might be tricky to figure out the heuristic at each step.
Challenge
You have a knapsack and
n items. You would like to fit as many items as possible but you know that the knapsack will tear apart if the items in it are too heavy (if the total weight exceeds the threshold t). You’d like to know the maximum number of items you can put in your bag so that it’s okay to carry it.Input
The first line of the input contains two integers
n (1 ≤ n ≤ ) and t (1 ≤ t ≤ ) - the number of items and the maximum threshold the knapsack can carry.The next line contains
n space-separated integers Output
The program should print the maximum number of items you can carry.
Examples
Input | Output |
7 10
4 1 2 5 8 7 1 | 4 |
Explanation
We can carry
1, 2, 5, 1, or 4, 1, 2, 1, or 1, 2, 7, 1. For all of the cases there are 4 items in total.Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB