Greedy Algorithms VTU BCSL40A

Greedy (Fractional) Knapsack

The Fractional Knapsack problem uses a greedy approach — selecting items by highest value-to-weight ratio — allowing fractional items to maximize profit.

Time Complexity

O(n²)

Space Complexity

O(1)

Paradigm

Greedy Algorithms

Introduction

The Greedy (Fractional) Knapsack Problem allows items to be split, unlike the 0/1 version. This makes the greedy approach optimal: always pick the item with the highest profit-to-weight ratio. If the item doesn't fully fit, take a fraction of it. This gives the maximum possible profit for the given capacity.

Problem Statement

Given n items with weights and profits and a knapsack of capacity W, maximize the total profit. Items can be added fractionally (any portion of an item can be taken).

Real World Applications

→ Cutting stock problems in manufacturing
→ Loading bulk cargo (liquids, grains) with weight limits
→ Bandwidth allocation in networks
→ Investment portfolio management
→ Advertisement budget allocation

Algorithm Explanation

For each remaining item, compute profit/weight ratio. Pick the item with the highest ratio. If it fits entirely, take the full item. If not, take the fraction that fills the remaining capacity. Repeat until the knapsack is full or all items are considered.

Step-by-Step Procedure

1 Read number of items n, weights, values, and maximum capacity.
2 While capacity > 0:
3 Find item with maximum profit/weight ratio among remaining items.
4 If item weight ≤ remaining capacity: take the whole item.
5 Else: take a fraction = remaining_capacity/item_weight.
6 Add profit to total. Mark item as used (set value to 0).
7 Print total maximum profit.

Complete C Program

Dis_knapsack.c

View on GitHub ↗

#include<stdio.h>
#include<stdlib.h>

int main() {
    int max_qty, n, m, array[2][20], i, j = 0;
    float sum = 0, max;
    printf("Enter the Number of Items: ");
    scanf("%d", &n);
    printf("Enter the Weights: ");
    for(i = 0; i < n; i++) scanf("%d", &array[0][i]);
    printf("Enter the Values: ");
    for(i = 0; i < n; i++) scanf("%d", &array[1][i]);
    printf("Enter the Maximum Capacity: ");
    scanf("%d", &max_qty);
    m = max_qty;
    while(m > 0) {
        max = 0;
        for(i = 0; i < n; i++) {
            if(((float)array[1][i] / (float)array[0][i]) > max) {
                max = (float)array[1][i] / (float)array[0][i];
                j = i;
            }
        }
        if(array[0][j] > m) {
            printf("Fraction of item %d added: %d units\n", j + 1, m);
            sum += m * max;
            m = -1;
        } else {
            printf("Full item %d added: %d units\n", j + 1, array[0][j]);
            m -= array[0][j];
            sum += (float)array[1][j];
            array[1][j] = 0;
        }
    }
    printf("Total Profit: %.2f\n", sum);
    return 0;
}

Sample Input & Output

Sample Input

Expected Output

Full item 3 added: 30 units
Full item 2 added: 20 units
Fraction of item 1 added: 0 units
Total Profit: 240.00

Dry Run / Trace

Items: w=[10,20,30], v=[60,100,120], W=50.
Ratios: 6, 5, 4. Pick item 1 (ratio 6), take full 10 units, profit=60, W=40.
Pick item 2 (ratio 5), take full 20 units, profit=160, W=20.
Pick item 3 (ratio 4), take 20/30 fraction, profit=160+80=240, W=0.
Total = 240.

Advantages & Disadvantages

✓ Advantages

+ Optimal solution guaranteed for fractional knapsack
+ Greedy approach is simple and fast
+ O(n log n) with sorting, O(n²) without
+ Easier to implement than DP

✗ Disadvantages

− Not applicable when items cannot be split (use 0/1 knapsack)
− Greedy does not work for 0/1 knapsack
− Does not track exact items selected (fractions)

Viva Questions & Answers

Q1. Why does greedy work for Fractional Knapsack but not 0/1 Knapsack?

In fractional knapsack, we can take fractions so the greedy choice (highest ratio) is always globally optimal. In 0/1, we may need to skip a high-ratio item to fit more valuable combinations.

Q2. What is the optimal greedy criterion for Fractional Knapsack?

Sort items by profit/weight ratio in decreasing order and greedily pick items.

Q3. What is the time complexity with sorting?

O(n log n) for sorting + O(n) for the greedy selection = O(n log n) overall.

Q4. Can the fractional knapsack have a better profit than 0/1 knapsack?

Yes, since fractional knapsack allows fractions, it can achieve at least as much profit as 0/1 knapsack, and often more.

Q5. What happens when all items have the same profit/weight ratio?

Any order of selection gives the same maximum profit.