Imagine you have n items of size `items[i]` each one. Your goal is to put as many items as possible in the box of size `N`, i. e. choose some objects whose summary size is less or equal to size of the box `N`.

It's not so hard to understand that you have to choose smaller items first, and you can do it until there is an empty place. If you have `items = [2, 1, 5, 5, 3, 7, 6]` and `N = 13`, you put items of size 1, 2, 3, 5 and receive 4 items in the box. You can’t put any other item, because left empty space has size 2 and it is not enough. The smaller item you choose every time, the more space is left, and the more other items you can put in.

So, the algorithm is following:

def maxItems(items, n):
  items.sort() # reorder items in ascending order
  ans = 0
  for item in items:
    n -= item # reduce the empty space
    if n < 0:
      break
    ans+=1 # if some empty space left, item is added
  return ans


Meet the Greedy Algorithms course that introduces you the Greedy paradigm, which can be used in a huge amount of problems. We’ll start with classic problems, then move to the Greedy Algorithms in arrays, and finish with the hardest part – Greedy Algorithms on graphs, such as Kruskal’s Minimum Spanning Tree and Dijkstra Shortest Path Algorithm.

That would be great if you’re already familiar with Algorithms at all and such concepts as Dynamic Programming.

The Greedy Approach is to build solutions piece by piece, always choosing the most relevant and beneficial one, to achieve the optimal solution.

There is a set of interesting and non-trivial problems on arrays that use the Greedy approach.

This chapter is dedicated to different approaches to find minimum-weighted paths on graphs. We work with oriented weighted graphs here.

Description and Simple Example

Soluzione

Description and Simple Example

Soluzione