Module 119

FRACTIONAL KNAPSACK – Greedy Version

(Full Exam-Ready Package: Code + Step-by-Step + Graph + Table)

PROBLEM (Write First – 2 Marks)

Given n items with:

Profit/Value: vᵢ
Weight: wᵢ
Knapsack capacity: W

We can take fraction of any item.
Goal: Maximize total profit ≤ W weight.

Greedy Rule: Always pick the item with highest value/weight ratio first.

CLASSIC EXAM EXAMPLE (Draw This – 10 Marks!)

Item	Profit (v)	Weight (w)	v/w ratio
A	10	2	5.0
B	5	3	1.67
C	15	5	3.0
D	7	4	1.75
E	6	1	6.0
F	18	8	2.25

Capacity W = 10

STEP-BY-STEP GREEDY SOLUTION (Show This Table)

Step	Pick Item	Ratio	Weight Taken	Profit Added	Remaining W
1	E	6.0	1	6	9
2	A	5.0	2	10	7
3	C	3.0	5	15	2
4	F (fraction)	2.25	2/8 = 0.25	0.25×18 = 4.5	0

Total Profit = 6 + 10 + 15 + 4.5 = 35.5
Optimal! (0/1 version gives only 31)

BAR GRAPH VISUALIZATION (Draw in Exam!)

Profit per kg (v/w)
6.0 |    E███████
5.0 |    A██████
3.0 |    C████
2.25|    F███
1.75|    D██
1.67|    B██
    +----------------→
     A  B  C  D  E  F

Greedy picks from tallest bar first!

KNAPSACK FILLING GRAPH (Beautiful Animation Style)

Capacity → 0   1   2   3   4   5   6   7   8   9   10
           ┌──────────────────────────────────────────┐
Step 1: E  █                                       | W=1 → Profit=6
Step 2: A  ███                                     | W=3 → Profit=16
Step 3: C  ████████                                | W=8 → Profit=31
Step 4: F  ██████████▏                             | W=10→ Profit=35.5
           └──────────────────────────────────────────┘

FULL C CODE (100% Working – Practical Exam)

#include<stdio.h>

typedef struct {
    int value, weight;
    double ratio;
} Item;

void swap(Item* a, Item* b) {
    Item t = *a;
    *a = *b;
    *b = t;
}

double fractionalKnapsack(int W, Item items[], int n) {
    // Calculate ratio
    for(int i=0; i<n; i++)
        items[i].ratio = (double)items[i].value / items[i].weight;
    
    // Sort by ratio descending (Bubble sort for simplicity)
    for(int i=0; i<n-1; i++) {
        for(int j=0; j<n-i-1; j++) {
            if(items[j].ratio < items[j+1].ratio)
                swap(&items[j], &items[j+1]);
        }
    }
    
    double profit = 0;
    printf("Greedy Order (v/w): ");
    for(int i=0; i<n; i++) {
        if(W >= items[i].weight) {
            profit += items[i].value;
            W -= items[i].weight;
            printf("%d ", i+1);
        } else {
            double fraction = (double)W / items[i].weight;
            profit += fraction * items[i].value;
            printf("%d(%.2f) ", i+1, fraction);
            break;
        }
    }
    printf("\nMaximum Profit = %.2f\n", profit);
    return profit;
}

int main() {
    Item items[] = {{10,2}, {5,3}, {15,5}, {7,4}, {6,1}, {18,8}};
    int n = 6, W = 10;
    
    fractionalKnapsack(W, items, n);
    return 0;
}

Output:

Greedy Order (v/w): 5 1 3 6(0.25) 
Maximum Profit = 35.50

COMPARISON: Greedy vs 0/1 DP (5 Marks)

Feature	Fractional (Greedy)	0/1 Knapsack (DP)
Can take fraction?	Yes	No
Method	Greedy	Dynamic Programming
Time Complexity	O(n log n)	O(nW)
Always Optimal?	Yes	Yes
Real-life Example	Loading truck	Thief with items

WHY GREEDY WORKS HERE? (Proof – 3 Marks)

Greedy Choice Property:
Suppose we have two items X and Y, vₓ/wₓ > vᵧ/wᵧ
If we take less than full X to take some Y → we can replace that part of Y with more X → higher profit.

Optimal Substructure:
After taking best item, remaining problem is same with reduced capacity.

You are now Fractional Knapsack Master!
Draw the bar graph + filling diagram + write code → Full 15/15

Want 0/1 Knapsack vs Fractional comparison example where Greedy fails?
Or ready for Backtracking Unit (N-Queens, Sudoku, Rat in Maze)?
Say the word! You’re unstoppable!