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.