DSA Notes

Hub Algorithm vs Data Structure - Key Differences Real-World Applications of DSA Time and Space Complexity Overview What is DSA? Data Structures and Algorithms Why Learn Data Structures and Algorithms Asymptotic Analysis - Understanding Algorithm Growth Best, Average, and Worst Case Analysis Big O Notation - Upper Bound Analysis Big Omega Notation - Lower Bound Analysis Big Theta Notation - Tight Bound Analysis Space Complexity - Memory Analysis Time Complexity Examples and Analysis Array Interview Problems and Solutions Array Operations - Insert, Delete, Search Array Rotation Techniques Array Searching Techniques Arrays - Fundamental Data Structure Dynamic Arrays - Flexible Sizing Multidimensional Arrays - 2D and Beyond Sliding Window Technique for Arrays Anagram Problems - Character Rearrangement Palindrome Problems and Solutions Pattern Searching in Strings String Interview Problems Collection String Matching Algorithms - Pattern Searching String Operations - Concatenation, Substring, Manipulation String Data Structure - Fundamentals Circular Linked List - Ring Structure Doubly Linked List - Bidirectional Traversal Linked List Interview Problems Linked List - Data Structure Fundamentals Linked List Operations - Insert, Delete, Reverse Reverse Linked List - Iterative and Recursive Singly Linked List - Implementation and Operations Balanced Parentheses - Stack Application Infix, Prefix, Postfix Expressions - Stack Application Stack Implementation Techniques Stack Interview Problems and Solutions Stack Data Structure - LIFO Principle Stack using Arrays - Static Implementation Stack using Linked Lists - Dynamic Implementation Circular Queue - Efficient Space Usage Deque (Double Ended Queue)Priority Queue - Custom Ordering Queue Applications - Real-World Use Cases Queue Implementation - Array and Linked List Queue Interview Problems and Solutions Queue Data Structure - FIFO Principle AVL Tree - Self-Balancing Binary Search Tree Binary Search Tree (BST)Binary Tree - Structure and Operations Fenwick Tree (Binary Indexed Tree)Red-Black Tree - Another Balanced BST Segment Tree - Range Query Data Structure Tree Interview Problems Collection Tree Data Structure Fundamentals Tree Traversals - Inorder, Preorder, Postorder, Level Order Heap Data Structure Heap Operations Heap Interview Problems Max-Heap Min-Heap Implementation and Use Cases Priority Queue using Heap Bellman-Ford Algorithm Breadth-First Search (BFS) Algorithm Depth-First Search (DFS) Algorithm Dijkstra\Floyd-Warshall Algorithm Graph Interview Problems Graph Data Structure Fundamentals Graph Representation Methods Kruskal\Minimum Spanning Tree (MST)Prim\Shortest Path Algorithms: Complete Comparison Topological Sorting Union-Find (Disjoint Set Union)Separate Chaining Collision Handling Hash Functions Hashing Fundamentals Hashing Interview Problems Open Addressing Bubble Sort - Simple Sorting Algorithm Counting Sort - Non-Comparison Sorting Heap Sort - Heap Based Sorting Insertion Sort - Build Sorted Array Merge Sort - Divide and Conquer Quick Sort - Partition Based Sorting Radix Sort - Digit Based Sorting Selection Sort - Selection Based Sorting Sorting Algorithms Comparison - Choosing the Right Algorithm Sorting Algorithms - Fundamentals and Concepts Binary Search - Efficient Searching Interpolation Search - Intelligent Searching Linear Search - Sequential Search Algorithm Search Algorithms Comparison Searching Algorithm Interview Problems Ternary Search Algorithm Backtracking with Recursion Recursion Fundamentals - Base Case and Recurrence Recursion Problems and Solutions Recursion Tree - Visualizing Function Calls Recursion vs Iteration - Comparing Approaches Tail Recursion - Optimization Technique Dynamic Programming Interview Problems Dynamic Programming Fundamentals Fibonacci with Dynamic Programming 0/1 Knapsack Problem Longest Common Subsequence (LCS)Longest Increasing Subsequence (LIS)Matrix Chain Multiplication Memoization (Top-Down Dynamic Programming)Tabulation (Bottom-Up Dynamic Programming)Activity Selection Problem Fractional Knapsack Greedy Interview Problems Greedy Algorithm Fundamentals Huffman Coding — Data Structures & Algorithms Job Sequencing with Deadlines Backtracking Fundamentals Backtracking Practice Problems N-Queens Problem Rat in a Maze Subset Generation Sudoku Solver Codeforces Guide for Competitive Programmers Common Competitive Programming Techniques Contest Strategies for Competitive Programming Competitive Programming Introduction Fast Input/Output for Competitive Programming LeetCode Guide for Interview Preparation Bit Manipulation - Advanced Techniques Bloom Filter - Probabilistic Data Structure Computational Geometry - Algorithms and Techniques Disjoint Set Union (DSU) - Union Find Randomized Algorithms - Probabilistic Computing Skip List - Probabilistic Balanced Structure Suffix Array - String Indexing Trie - Prefix Tree for Efficient Searching Autocomplete System Using Trie Library Management System Using DSA Route Finder Using Graphs Mini Search Engine Project Social Network Analysis Using Graphs Essential Coding Patterns for Interviews DSA Cheatsheet: Quick Reference Essential DSA Interview Questions FAANG DSA Sheet: Company-Specific Patterns and Problems Problem Solving Strategies for Coding Interviews Complexity Cheatsheet Important Algorithms Summary Best Practice Platforms for DSA Recommended Books for DSA

Fractional Knapsack

Solve the Fractional Knapsack problem using a greedy approach — sort by value-to-weight ratio, fill optimally, and understand why fractions make greedy work.

Problem Statement

Given N items, each with a weight and value, and a knapsack with maximum capacity W, maximize the total value you can carry. Unlike the 0/1 Knapsack, here you can take fractions of items — you might take half of an item, getting half its value at half its weight.

Why Greedy Works for Fractional (But Not 0/1)

When you can take fractions, there is no "wasted capacity" dilemma. You can always fill the knapsack completely by taking a fraction of the last item. This means the locally optimal choice (highest value per unit weight) never blocks a better option — the greedy choice property holds.

For 0/1 Knapsack, taking a high-ratio item might consume too much capacity, preventing two smaller items that together would be more valuable. Fractions eliminate this problem entirely.

Algorithm

Compute the value-to-weight ratio for each item: ratio[i] = value[i] / weight[i]
Sort items by ratio in descending order (most valuable per kg first)
Greedily take items:

If the full item fits, take it entirely
If it does not fit, take the fraction that fills the remaining capacity

Stop when the knapsack is full

Dry Run Example

Knapsack capacity	W = 50
Item A: weight=10, value=60	ratio=6.0
Item B: weight=20, value=100	ratio=5.0
Item C: weight=30, value=120	ratio=4.0
Sorted by ratio	A(6.0), B(5.0), C(4.0)
Step 1	Take all of A. Remaining capacity = 50-10 = 40. Value = 60.
Step 2	Take all of B. Remaining capacity = 40-20 = 20. Value = 60+100 = 160.
Step 3	C weighs 30, but only 20 capacity left.
Result	Total value = 240 (knapsack is full at exactly 50).

Compare with 0/1 Knapsack:

Taking A+B = weight 30, value 160 → cannot take C (weight 30 > remaining 20)
Taking B+C = weight 50, value 220
Optimal 0/1 = 220. But fractional = 240 (always ≥ 0/1 solution).

Python Implementation

Example

def fractional_knapsack(items, capacity): """ items: list of (weight, value) tuples capacity: maximum weight the knapsack can hold Returns: maximum total value achievable """ # Calculate ratio and sort descending ratios = [(value / weight, weight, value) for weight, value in items] ratios.sort(reverse=True) total_value = 0.0 remaining = capacity for ratio, weight, value in ratios: if remaining <= 0: break if weight <= remaining: # Take the whole item total_value += value remaining -= weight else: # Take fraction fraction = remaining / weight total_value += value * fraction remaining = 0 return total_value # Test items = [(10, 60), (20, 100), (30, 120)] capacity = 50 print(f"Maximum value: {fractional_knapsack(items, capacity)}") # Maximum value: 240.0

C++ Implementation

cpp example

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

struct Item {
    int weight, value;
    double ratio() const { return (double)value / weight; }
};

double fractionalKnapsack(vector<Item>& items, int capacity) {
    sort(items.begin(), items.end(), [](const Item& a, const Item& b) {
        return a.ratio() > b.ratio();
    });
    
    double totalValue = 0.0;
    int remaining = capacity;
    
    for (const Item& item : items) {
        if (remaining <= 0) break;
        
        if (item.weight <= remaining) {
            totalValue += item.value;
            remaining -= item.weight;
        } else {
            double fraction = (double)remaining / item.weight;
            totalValue += item.value * fraction;
            remaining = 0;
        }
    }
    return totalValue;
}

int main() {
    vector<Item> items = {{10, 60}, {20, 100}, {30, 120}};
    cout << "Max value: " << fractionalKnapsack(items, 50) << endl; // 240
}

Detailed Implementation with Item Tracking

Often you need to know *what* was taken, not just the total value:

Example

def fractional_knapsack_detailed(items, capacity): n = len(items) # (ratio, original_index) order = sorted(range(n), key=lambda i: items[i][1]/items[i][0], reverse=True) taken = [0.0] * n # fraction taken of each item total_value = 0.0 remaining = capacity for idx in order: weight, value = items[idx] if remaining <= 0: break if weight <= remaining: taken[idx] = 1.0 total_value += value remaining -= weight else: fraction = remaining / weight taken[idx] = fraction total_value += value * fraction remaining = 0 return total_value, taken items = [(10, 60), (20, 100), (30, 120)] value, fractions = fractional_knapsack_detailed(items, 50) for i, (w, v) in enumerate(items): print(f"Item {i} (w={w}, v={v}): take {fractions[i]*100:.1f}%") # Item 0 (w=10, v=60): take 100.0% # Item 1 (w=20, v=100): take 100.0% # Item 2 (w=30, v=120): take 66.7%

Proof of Optimality

Claim: Sorting by value/weight ratio and greedily filling gives maximum value.

Proof (exchange argument):

Let items be sorted: r₁ ≥ r₂ ≥ ... ≥ rₙ (ratios).
Suppose optimal solution O takes fraction fᵢ of item i, and greedy solution G takes fraction gᵢ.
Find the first item j where gⱼ > fⱼ (greedy takes more of a high-ratio item).
In O, increase fⱼ and decrease some fₖ (k > j, lower ratio) by the same weight.
Value change: +Δw×rⱼ - Δw×rₖ ≥ 0 (since rⱼ ≥ rₖ). Solution improves or stays equal.
Repeat until O matches G. Therefore G is optimal. ∎

Complexity Analysis

Operation	Time	Space
Compute ratios	O(n)	O(n)
Sort by ratio	O(n log n)	O(1) extra (in-place)
Greedy selection	O(n)	O(1)
Total	O(n log n)	O(n)

Fractional vs 0/1 Knapsack Comparison

Aspect	Fractional	0/1
Items divisible?	Yes	No
Algorithm	Greedy	Dynamic Programming
Time complexity	O(n log n)	O(n × W)
Greedy works?	Yes	No
Solution ≥	Always ≥ 0/1 optimal	—

The fractional solution is always an upper bound on the 0/1 solution, which is useful in branch-and-bound algorithms for the 0/1 variant.

Real-World Applications

Investment portfolios: Allocate budget across stocks (can buy fractional shares)
Resource loading: Fill a truck with divisible goods (grains, liquids)
CPU scheduling: Allocate fractional time slices to tasks by priority/value
Memory allocation: Allocate proportional memory to processes by importance
Ad slot allocation: Divide advertising time by revenue rate

Key Takeaways

The Fractional Knapsack is the simplest greedy optimization problem: sort by value density, fill greedily. The ability to take fractions eliminates the "blocking" problem that makes 0/1 Knapsack hard. Remember: fractional solution upper-bounds 0/1 solution, O(n log n) time, and the exchange argument provides a clean optimality proof.

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Fractional Knapsack.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this Data Structures & Algorithms topic.

Search Terms

data-structures-algorithms, data structures & algorithms, data, structures, algorithms, greedy, fractional, knapsack

Related Data Structures & Algorithms Topics

Continue learning this concept

Greedy AlgorithmsActivity Selection ProblemSolve the Activity Selection problem with a greedy approach — sort by finish time, select non-overlapping activities, and prove optimality via exchange argument.Greedy AlgorithmsGreedy Interview ProblemsMaster four classic greedy interview problems — Minimum Platforms, Gas Station Circuit, Jump Game, and Candy Distribution with detailed approaches and code.Greedy AlgorithmsGreedy Algorithm FundamentalsUnderstand greedy algorithms — the greedy choice property, optimal substructure, when greedy works vs fails, and techniques to prove correctness.Greedy AlgorithmsHuffman Coding — Data Structures & AlgorithmsBuild Huffman codes from scratch — understand frequency-based prefix codes, priority queue construction, tree building, encoding/decoding, and compression analysis.Greedy AlgorithmsJob Sequencing with DeadlinesSolve the Job Sequencing problem using a greedy approach — maximize profit by sorting by profit and assigning each job to the latest available time slot before its deadline.Dynamic Programming0/1 Knapsack ProblemMaster the classic 0/1 Knapsack problem with 2D DP table construction, include/exclude decisions, solution traceback, and space optimization.

PreviousActivity Selection Problem NextGreedy Interview Problems

DSA Notes

Fractional Knapsack

Solve the Fractional Knapsack problem using a greedy approach — sort by value-to-weight ratio, fill optimally, and understand why fractions make greedy work.

Problem Statement

Why Greedy Works for Fractional (But Not 0/1)

For 0/1 Knapsack, taking a high-ratio item might consume too much capacity, preventing two smaller items that together would be more valuable. Fractions eliminate this problem entirely.

Algorithm

Compute the value-to-weight ratio for each item: ratio[i] = value[i] / weight[i]
Sort items by ratio in descending order (most valuable per kg first)
Greedily take items:

If the full item fits, take it entirely
If it does not fit, take the fraction that fills the remaining capacity

Stop when the knapsack is full

Dry Run Example

Knapsack capacity	W = 50
Item A: weight=10, value=60	ratio=6.0
Item B: weight=20, value=100	ratio=5.0
Item C: weight=30, value=120	ratio=4.0
Sorted by ratio	A(6.0), B(5.0), C(4.0)
Step 1	Take all of A. Remaining capacity = 50-10 = 40. Value = 60.
Step 2	Take all of B. Remaining capacity = 40-20 = 20. Value = 60+100 = 160.
Step 3	C weighs 30, but only 20 capacity left.
Result	Total value = 240 (knapsack is full at exactly 50).

Compare with 0/1 Knapsack:

Taking A+B = weight 30, value 160 → cannot take C (weight 30 > remaining 20)
Taking B+C = weight 50, value 220
Optimal 0/1 = 220. But fractional = 240 (always ≥ 0/1 solution).

Python Implementation

Example

C++ Implementation

cpp example

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

struct Item {
    int weight, value;
    double ratio() const { return (double)value / weight; }
};

double fractionalKnapsack(vector<Item>& items, int capacity) {
    sort(items.begin(), items.end(), [](const Item& a, const Item& b) {
        return a.ratio() > b.ratio();
    });
    
    double totalValue = 0.0;
    int remaining = capacity;
    
    for (const Item& item : items) {
        if (remaining <= 0) break;
        
        if (item.weight <= remaining) {
            totalValue += item.value;
            remaining -= item.weight;
        } else {
            double fraction = (double)remaining / item.weight;
            totalValue += item.value * fraction;
            remaining = 0;
        }
    }
    return totalValue;
}

int main() {
    vector<Item> items = {{10, 60}, {20, 100}, {30, 120}};
    cout << "Max value: " << fractionalKnapsack(items, 50) << endl; // 240
}

Detailed Implementation with Item Tracking

Often you need to know *what* was taken, not just the total value:

Example

Proof of Optimality

Claim: Sorting by value/weight ratio and greedily filling gives maximum value.

Proof (exchange argument):

Let items be sorted: r₁ ≥ r₂ ≥ ... ≥ rₙ (ratios).
Suppose optimal solution O takes fraction fᵢ of item i, and greedy solution G takes fraction gᵢ.
Find the first item j where gⱼ > fⱼ (greedy takes more of a high-ratio item).
In O, increase fⱼ and decrease some fₖ (k > j, lower ratio) by the same weight.
Value change: +Δw×rⱼ - Δw×rₖ ≥ 0 (since rⱼ ≥ rₖ). Solution improves or stays equal.
Repeat until O matches G. Therefore G is optimal. ∎

Complexity Analysis

Operation	Time	Space
Compute ratios	O(n)	O(n)
Sort by ratio	O(n log n)	O(1) extra (in-place)
Greedy selection	O(n)	O(1)
Total	O(n log n)	O(n)

Fractional vs 0/1 Knapsack Comparison

Aspect	Fractional	0/1
Items divisible?	Yes	No
Algorithm	Greedy	Dynamic Programming
Time complexity	O(n log n)	O(n × W)
Greedy works?	Yes	No
Solution ≥	Always ≥ 0/1 optimal	—

The fractional solution is always an upper bound on the 0/1 solution, which is useful in branch-and-bound algorithms for the 0/1 variant.

Real-World Applications

Investment portfolios: Allocate budget across stocks (can buy fractional shares)
Resource loading: Fill a truck with divisible goods (grains, liquids)
CPU scheduling: Allocate fractional time slices to tasks by priority/value
Memory allocation: Allocate proportional memory to processes by importance
Ad slot allocation: Divide advertising time by revenue rate

Key Takeaways

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Fractional Knapsack.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this Data Structures & Algorithms topic.

Search Terms

data-structures-algorithms, data structures & algorithms, data, structures, algorithms, greedy, fractional, knapsack

Related Data Structures & Algorithms Topics

Continue learning this concept

PreviousActivity Selection Problem NextGreedy Interview Problems