Fractional Knapsack by Ratio
Take the highest value-per-weight first.
Fractional Knapsack by Ratio is a free Coding Interview Prep lesson on CoddyKit — lesson 3 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the Coding Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
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.
Value Per Weight
The key metric is each item's ratio of value to weight. A high ratio means a lot of value packed into very little space.
ratio = value / weightSort by Best Ratio
Sort items by value per weight, highest first. The greedy plan is to keep grabbing the densest value available.
items.sort(key=lambda i: i[0] / i[1], reverse=True)Take Whole While It Fits
Walk the sorted list and take each item fully if it still fits in the remaining capacity. Add its full value to your total.
if weight <= cap:
total += value
cap -= weightFill the Last Gap
When an item is too big, take a fraction that exactly fills the leftover space. Then the bag is full and you stop.
total += value * (cap / weight)Why Ratio Order Works
Each unit of capacity should hold the most value possible, so the densest item must go first. Swapping in lower density only loses value.
0/1 Knapsack Is Different
If items cannot be split, greedy by ratio breaks. The 0/1 version needs dynamic programming, not this simple sort.
The Running Time
Sorting by ratio costs O(n log n), and the fill loop is linear. That is plenty fast for typical contest limits.
Watch the Final Fraction
Use floating point or exact rationals for the partial item. Truncating early can shave value and cause a wrong answer.
Where It Shows Up
Think loading cargo, mixing fuels, or splitting resources. Whenever pieces are divisible, the ratio greedy is your tool.
Quick Check
You are filling a bag in the fractional knapsack problem.
Recap
Sort items by value per weight, take whole items while they fit, then a fraction to top off the bag. This greedy is optimal only when items split. 🚀
Frequently asked questions
Is the “Fractional Knapsack by Ratio” lesson free?
Yes — the full text of “Fractional Knapsack by Ratio” is free to read here on the web, and the Coding Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the Coding Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Fractional Knapsack by Ratio”?
Take the highest value-per-weight first. You practise Coding Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start Coding Interview Prep?
No prior experience is required. Coding Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 3 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Fractional Knapsack by Ratio” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this Coding Interview Prep lesson?
Yes. Every Coding Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- The Greedy Mindset
- Activity Selection by Earliest Finish
- Fractional Knapsack by Ratio
- Spot When Greedy Fails