Fractional Knapsack Problem in DSA C - Build from Scratch

Fractional Knapsack Problem

📖 Scenario: You are packing a bag for a hiking trip. You have several items, each with a weight and a value. Your bag can only carry a limited weight. You want to maximize the total value of items in your bag. You can take fractions of items if needed.

🎯 Goal: Build a program that calculates the maximum value you can carry in your bag using the fractional knapsack approach.

📋 What You'll Learn

Create an array of items with exact weights and values

Create a variable for the maximum weight the bag can carry

Calculate the maximum value by taking whole or fractional parts of items

Print the maximum value with two decimal places

💡 Why This Matters

🌍 Real World

Fractional knapsack is used in resource allocation problems where partial resources can be used, such as loading cargo, budgeting, and cutting materials.

💼 Career

Understanding knapsack problems helps in optimization tasks in software engineering, logistics, finance, and operations research.

1

Create the items array

Create a struct called Item with weight and value as float. Then create an array called items with these exact entries: {weight: 10, value: 60}, {weight: 20, value: 100}, {weight: 30, value: 120}.

DSA C

# Define struct Item and create the items array
// Your code here

Hint

Use a struct to hold weight and value. Then create an array with the exact values.

2

Set the maximum bag weight

Create a float variable called maxWeight and set it to 50.

DSA C

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

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

// Create maxWeight variable
// Your code here

Hint

Use a float variable named maxWeight and assign 50 to it.

3

Calculate maximum value using fractional knapsack

Write a function called fractionalKnapsack that takes Item items[], int n, and float maxWeight. It returns a float maximum value. Sort items by value/weight ratio descending. Then pick items fully or partially until maxWeight is reached. Store the result in a variable called maxValue.

DSA C

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

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

float maxWeight = 50;

// Write fractionalKnapsack function and call it
// Your code here

Hint

Sort items by value/weight ratio. Then add full or fractional items until maxWeight is reached.

4

Print the maximum value

Write a printf statement to print maxValue with two decimal places.

DSA C

#include 
#include 

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

int compare(const void *a, const void *b) {
    Item *itemA = (Item *)a;
    Item *itemB = (Item *)b;
    float r1 = itemA->value / itemA->weight;
    float r2 = itemB->value / itemB->weight;
    if (r2 > r1) return 1;
    else if (r2 < r1) return -1;
    else return 0;
}

float fractionalKnapsack(Item items[], int n, float maxWeight) {
    qsort(items, n, sizeof(Item), compare);
    float maxValue = 0.0;
    float remainingWeight = maxWeight;
    for (int i = 0; i < n; i++) {
        if (items[i].weight <= remainingWeight) {
            maxValue += items[i].value;
            remainingWeight -= items[i].weight;
        } else {
            maxValue += items[i].value * (remainingWeight / items[i].weight);
            break;
        }
    }
    return maxValue;
}

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

float maxWeight = 50;

float maxValue = fractionalKnapsack(items, 3, maxWeight);

// Print maxValue with two decimal places
// Your code here

Hint

Use printf with format %.2f to print maxValue with two decimals.

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