Fractional Knapsack Problem in DSA C

Mental Model

We want to fill a bag with items to get the most value, and we can take parts of items if needed.

Analogy: Imagine filling a jar with different types of honey jars. You want the sweetest honey first, and if the jar is almost full, you take only part of the last honey jar.

Knapsack capacity: [__________] (empty)
Items sorted by value/weight ratio:
Item1(value=60, weight=10) -> ratio=6
Item2(value=100, weight=20) -> ratio=5
Item3(value=120, weight=30) -> ratio=4

Dry Run Walkthrough

Input: items: [(value=60, weight=10), (value=100, weight=20), (value=120, weight=30)], knapsack capacity=50

Goal: Maximize total value in knapsack by taking whole or fractional parts of items

Step 1: Sort items by value/weight ratio descending

Items order: (60,10) ratio=6 -> (100,20) ratio=5 -> (120,30) ratio=4

Why: We want to pick items with highest value per weight first to maximize value

Step 2: Take whole item 1 (weight 10) into knapsack

Knapsack: 10/50 filled, total value=60

Why: Item 1 fits fully, so take it all

Step 3: Take whole item 2 (weight 20) into knapsack

Knapsack: 30/50 filled, total value=160

Why: Item 2 fits fully, so take it all

Step 4: Take fraction of item 3 to fill remaining capacity (20/30 fraction)

Knapsack: 50/50 filled, total value=160 + (120 * 20/30) = 240

Why: Only part of item 3 fits, so take fraction to fill knapsack

Result:

Knapsack full: total value=240

Annotated Code

DSA C

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

// Structure to store item value and weight
typedef struct {
    int value;
    int weight;
    double ratio;
} Item;

// Comparator to sort items by value/weight ratio descending
int cmp(const void *a, const void *b) {
    Item *item1 = (Item *)a;
    Item *item2 = (Item *)b;
    if (item2->ratio > item1->ratio) return 1;
    else if (item2->ratio < item1->ratio) return -1;
    else return 0;
}

// Function to solve fractional knapsack
double fractionalKnapsack(Item items[], int n, int capacity) {
    // Calculate ratio for each item
    for (int i = 0; i < n; i++) {
        items[i].ratio = (double)items[i].value / items[i].weight;
    }

    // Sort items by ratio descending
    qsort(items, n, sizeof(Item), cmp);

    double totalValue = 0.0;
    int remaining = capacity;

    for (int i = 0; i < n; i++) {
        if (items[i].weight <= remaining) {
            // Take whole item
            totalValue += items[i].value;
            remaining -= items[i].weight;
        } else {
            // Take fraction of item
            totalValue += items[i].ratio * remaining;
            break; // Knapsack full
        }
    }
    return totalValue;
}

int main() {
    Item items[] = {{60, 10, 0}, {100, 20, 0}, {120, 30, 0}};
    int n = sizeof(items) / sizeof(items[0]);
    int capacity = 50;

    double maxValue = fractionalKnapsack(items, n, capacity);
    printf("Maximum value in knapsack = %.2f\n", maxValue);
    return 0;
}

items[i].ratio = (double)items[i].value / items[i].weight;

Calculate value per weight ratio for sorting priority

qsort(items, n, sizeof(Item), cmp);

Sort items by descending ratio to pick best value first

if (items[i].weight <= remaining) {

Check if whole item fits in remaining capacity

totalValue += items[i].value;

Add full item value to total

remaining -= items[i].weight;

Reduce remaining capacity by item weight

totalValue += items[i].ratio * remaining;

Add fractional value for partial item to fill knapsack

break;

Stop after filling knapsack with fraction

Output

Maximum value in knapsack = 240.00

Complexity Analysis

Time: O(n log n) because we sort n items by ratio, then iterate once over them

Space: O(n) for storing items and their ratios

vs Alternative: Better than trying all subsets (exponential), greedy sorting gives optimal fractional solution efficiently

Edge Cases

Empty items list

Returns 0 value since no items to take

DSA C

for (int i = 0; i < n; i++) {

Knapsack capacity zero

Returns 0 value since no capacity to take items

DSA C

int remaining = capacity;

Item with zero weight (invalid)

Division by zero avoided by input validation (not shown here), else program may crash

DSA C

items[i].ratio = (double)items[i].value / items[i].weight;

When to Use This Pattern

When you need to maximize value with divisible items and limited capacity, use the fractional knapsack greedy approach sorting by value/weight ratio.

Common Mistakes

Mistake: Sorting items by value or weight alone instead of value/weight ratio
Fix: Sort items by value divided by weight to prioritize best value per unit weight

Mistake: Not taking fractional part when item doesn't fully fit
Fix: Calculate fraction of item to fill remaining capacity and add proportional value

Summary

Find maximum value by taking whole or fractional parts of items to fill knapsack capacity.

Use when items can be divided and you want the best value for limited capacity.

Sort items by value/weight ratio and take as much as possible from highest ratio first.

Practice

1. What is the main goal of the Fractional Knapsack Problem?

easy

A. Select items only if their weight is less than a fixed number

B. Minimize total weight of items selected

C. Maximize total value by taking fractions of items within weight limit

D. Find the number of items that fit exactly in the knapsack

Solution

1. Step 1: Understand the problem goal

   The fractional knapsack problem allows taking parts of items to maximize total value within a weight limit.

2. Step 2: Compare options

   Only Maximize total value by taking fractions of items within weight limit correctly describes maximizing value by taking fractions within weight limit.

3. Final Answer:

   Maximize total value by taking fractions of items within weight limit -> Option C

4. Quick Check:

   Goal = Maximize value with fractions [OK]

Hint: Remember: fractional means partial items allowed [OK]

Common Mistakes:

• Thinking only whole items can be taken
• Confusing with minimizing weight
• Ignoring value maximization

2. Which of the following is the correct way to sort items by value-to-weight ratio in C for the fractional knapsack?

easy

A. qsort(items, n, sizeof(Item), compare); where compare sorts by value/weight descending

B. sort(items, items+n); without a comparator

C. qsort(items, n, sizeof(Item), compare); where compare sorts by weight ascending

D. Using bubble sort on values only

Solution

1. Step 1: Identify sorting requirement

   Items must be sorted by value-to-weight ratio descending for greedy selection.

2. Step 2: Match sorting method

   Using qsort with a comparator sorting by value/weight descending is correct.

3. Final Answer:

   qsort(items, n, sizeof(Item), compare); where compare sorts by value/weight descending -> Option A

4. Quick Check:

   Sort by value/weight ratio descending [OK]

Hint: Sort by value/weight ratio descending before picking [OK]

Common Mistakes:

• Sorting by weight only
• Sorting without comparator
• Using inefficient sorting for large data

3. What is the output of the following C code snippet for fractional knapsack?

typedef struct { int value; int weight; } Item;

Item items[] = {{60, 10}, {100, 20}, {120, 30}};
int n = 3, W = 50;

// Assume items sorted by value/weight descending
float fractionalKnapsack(Item items[], int n, int W) {
    int curWeight = 0;
    float finalValue = 0.0;
    for (int i = 0; i < n; i++) {
        if (curWeight + items[i].weight <= W) {
            curWeight += items[i].weight;
            finalValue += items[i].value;
        } else {
            int remain = W - curWeight;
            finalValue += items[i].value * ((float) remain / items[i].weight);
            break;
        }
    }
    return finalValue;
}

printf("%.2f", fractionalKnapsack(items, n, W));

medium

A. 240.00

B. 220.00

C. 180.00

D. 200.00

Solution

1. Step 1: Calculate value/weight ratios and sort

   Ratios: 60/10=6, 100/20=5, 120/30=4. Sorted order is as given.

2. Step 2: Add items until weight limit 50

   Add first item fully: weight=10, value=60; second fully: weight=30, value=160; third partially: remain=20, value=120*(20/30)=80; total value=60+100+80=240.

3. Final Answer:

   240.00 -> Option A

4. Quick Check:

   Sum values with fractions = 240.00 [OK]

Hint: Add full items then fraction of next to fill knapsack [OK]

Common Mistakes:

• Not sorting by ratio
• Adding partial value incorrectly
• Ignoring remaining capacity

4. Find the error in this C code snippet for fractional knapsack:

float fractionalKnapsack(Item items[], int n, int W) {
    int curWeight = 0;
    float finalValue = 0.0;
    for (int i = 0; i < n; i++) {
        if (curWeight + items[i].weight < W) {
            curWeight += items[i].weight;
            finalValue += items[i].value;
        } else {
            int remain = W - curWeight;
            finalValue += items[i].value * ((float) remain / items[i].weight);
            break;
        }
    }
    return finalValue;
}

medium

A. The remain calculation is incorrect

B. The finalValue should be int, not float

C. The loop should run from i=1 to n

D. The condition should be <= instead of < to include full weight equal to W

Solution

1. Step 1: Analyze the weight check condition

   The condition curWeight + items[i].weight < W excludes items that exactly fill the knapsack.

2. Step 2: Correct the condition

   Changing to <= allows taking items that fit exactly, avoiding missing full items.

3. Final Answer:

   The condition should be <= instead of < to include full weight equal to W -> Option D

4. Quick Check:

   Use <= to include exact weight [OK]

Hint: Use <= to allow full item if it fits exactly [OK]

Common Mistakes:

• Using < excludes exact fit items
• Changing variable types unnecessarily
• Incorrect loop indices

5. Given items with values and weights: {value: 40, weight: 2}, {value: 100, weight: 20}, {value: 50, weight: 10}, and a knapsack capacity of 26, what is the maximum value achievable using fractional knapsack?

hard

A. 190

B. 160

C. 180

D. 140

Solution

1. Step 1: Calculate value/weight ratios and sort items

   Ratios: 40/2=20, 100/20=5, 50/10=5. Sorted descending: {40,2}, {100,20}, {50,10}.

2. Step 2: Greedy selection with capacity 26

   Take {40,2} full: w=2, v=40, remain=24.
   Take {100,20} full: w=22, v=140, remain=4.
   Fraction of {50,10}: (4/10)*50=20, total v=160.

3. Final Answer:

   160 -> Option B

4. Quick Check:

   Max value by greedy fractions = 160 [OK]

Hint: Sort by ratio, take full items, then fraction of next [OK]

Common Mistakes:

• Ignoring sorting by ratio
• Taking items in wrong order
• Miscomputing fractional value