Knapsack Problem

Given a list of profit for each items, weight if each and a bag of weight W, that is the maximum profit

optimal for FKP but can be arbitrarily bad for typical Knapsack Problem
Steps
1. Sort all the items by the ratio of their profits to their weights: $\frac{p _{1}}{w _{1}} \geq \frac{p _{2}}{w _{2}} \dots \geq \frac{p _{n}}{w _{n}}$
2. Greedily pick items in this order as long as adding an item to our collection does not exceed the capacity
Modify greedy:
1. Sort all the items by the ratio of their profits to their weights: $\frac{p _{1}}{w _{1}} \geq \frac{p _{2}}{w _{2}} \dots \geq \frac{p _{n}}{w _{n}}$
2. Greedily pick items in this order as long as adding an item to our collection does not exceed the capacity
3. Take the best of algorithm 1’s solution or the most profitable item

StrixTheKiet Notes