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.
You have a knapsack and
nitems. 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.
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
(1 ≤ ≤ ) - the weights of each of the items.
The program should print the maximum number of items you can carry.
7 10 4 1 2 5 8 7 1
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.
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB