Зміст курсу
Greedy Algorithms using Python
Greedy Algorithms using Python
Description 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:
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
Завдання
Change maxItems() function to return not the number of items, but the list of items, that should be added to the box.
Завдання
Change maxItems() function to return not the number of items, but the list of items, that should be added to the box.
Перейдіть на комп'ютер для реальної практикиПродовжуйте з того місця, де ви зупинились, використовуючи один з наведених нижче варіантівВсе було зрозуміло?
Description 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:
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
Завдання
Change maxItems() function to return not the number of items, but the list of items, that should be added to the box.
Завдання
Change maxItems() function to return not the number of items, but the list of items, that should be added to the box.
Перейдіть на комп'ютер для реальної практикиПродовжуйте з того місця, де ви зупинились, використовуючи один з наведених нижче варіантівВсе було зрозуміло?
Description 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:
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
Завдання
Change maxItems() function to return not the number of items, but the list of items, that should be added to the box.
Завдання
Change maxItems() function to return not the number of items, but the list of items, that should be added to the box.
Перейдіть на комп'ютер для реальної практикиПродовжуйте з того місця, де ви зупинились, використовуючи один з наведених нижче варіантівВсе було зрозуміло?
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
Завдання
Change maxItems() function to return not the number of items, but the list of items, that should be added to the box.
Перейдіть на комп'ютер для реальної практикиПродовжуйте з того місця, де ви зупинились, використовуючи один з наведених нижче варіантівПерейдіть на комп'ютер для реальної практикиПродовжуйте з того місця, де ви зупинились, використовуючи один з наведених нижче варіантів