Notesale: Turn your study into money

Document Preview

Extracts from the notes are below, to see the PDF you'll receive please use the links above

---

Knapsack - Greedy Method
Explanation
The knapsack greedy method is a heuristic algorithm for solving the knapsack problem
...

The greedy method works by iteratively adding the item with the highest profit-to-weight ratio to
the knapsack until the knapsack is full or no more items with positive profit-to-weight ratios
remain
...


Algorithm
1
...

2
...

3
...

 Otherwise, do not add the item to the knapsack
...
Return the items in the knapsack
...
sort(key=lambda item: item[0] / item[1], reverse=True)
knapsack = []
for item in items:
if item[1] <= capacity:
knapsack
...
This item has a profit of 30 and a weight of 10, so the knapsack still has 5 units of capacity
remaining
...
This item has a profit of 20 and a
weight of 5, so the knapsack can still fit it
...

The greedy method will therefore return the following items:
[(30, 10), (20, 5)]
The total profit of these items is 50, which is the maximum possible profit that can be obtained
from a subset of these items with a total weight of 15
...
This is because the sorting step takes O(n log n) time, and the remaining steps take O(n)
time
...

 It is also a good approximation to the optimal solution
...

 It can also be sensitive to the order in which the items are sorted

---