Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.Description and Simple Example | Greedy Algorithms: Overview and Examples
Greedy Algorithms using Python
course content

Course Content

Greedy Algorithms using Python

Greedy Algorithms using Python

1. Greedy Algorithms: Overview and Examples
Why Greedy?Description and Simple ExampleSchedule ProblemEuclidean AlgorithmEgyptian Fraction ProblemJob Sequencing Problem
2. Greedy on Arrays
Make Arrays EqualMinimum Product SubsetJumping Frog
3. Greedy on Graphs
PreparationDijkstra Shortest Path AlgorithmKruskal’s MSTPrim's MST

bookDescription and Simple Example

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:


              
12345678910

            
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
copy

Task

Change maxItems() function to return not the number of items, but the list of items, that should be added to the box.

Switch to desktopSwitch to desktop for real-world practiceContinue from where you are using one of the options below
Everything was clear?

How can we improve it?

Thanks for your feedback!

Section 1. Chapter 2
toggle bottom row

bookDescription and Simple Example

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:


              
12345678910

            
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
copy

Task

Change maxItems() function to return not the number of items, but the list of items, that should be added to the box.

Switch to desktopSwitch to desktop for real-world practiceContinue from where you are using one of the options below
Everything was clear?

How can we improve it?

Thanks for your feedback!

Section 1. Chapter 2
toggle bottom row

bookDescription and Simple Example

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:


              
12345678910

            
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
copy

Task

Change maxItems() function to return not the number of items, but the list of items, that should be added to the box.

Switch to desktopSwitch to desktop for real-world practiceContinue from where you are using one of the options below
Everything was clear?

How can we improve it?

Thanks for your feedback!

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:


              
12345678910

            
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
copy

Task

Change maxItems() function to return not the number of items, but the list of items, that should be added to the box.

Switch to desktopSwitch to desktop for real-world practiceContinue from where you are using one of the options below
Section 1. Chapter 2
Switch to desktopSwitch to desktop for real-world practiceContinue from where you are using one of the options below
some-alt