Fractional Knapsack by Ratio
Take the highest value-per-weight first.
The Knapsack Setup
You have items with a value and a weight and a bag of limited capacity. The goal is to carry the most total value you can. 🎒
Fractional Means Splittable
In the fractional version you may take a piece of an item, like half a sack of grain. This freedom is what lets greedy win here.
All lessons in this course
- The Greedy Mindset
- Activity Selection by Earliest Finish
- Fractional Knapsack by Ratio
- Spot When Greedy Fails