Fractional Knapsack Problem in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Fractional Knapsack Calculation

What is the output of the following C code that calculates the maximum value for fractional knapsack given weights and values arrays?

DSA C

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

float fractionalKnapsack(int W, Item items[], int n) {
    float totalValue = 0.0;
    int i, curWeight = 0;
    float ratio[n];

    for (i = 0; i < n; i++) {
        ratio[i] = (float)items[i].value / items[i].weight;
    }

    for (i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            if (ratio[i] < ratio[j]) {
                float temp = ratio[i]; ratio[i] = ratio[j]; ratio[j] = temp;
                Item tempItem = items[i]; items[i] = items[j]; items[j] = tempItem;
            }
        }
    }

    for (i = 0; i < n; i++) {
        if (curWeight + items[i].weight <= W) {
            curWeight += items[i].weight;
            totalValue += items[i].value;
        } else {
            int remain = W - curWeight;
            totalValue += ratio[i] * remain;
            break;
        }
    }
    return totalValue;
}

#include <stdio.h>
int main() {
    Item items[] = {{60, 10}, {100, 20}, {120, 30}};
    int W = 50;
    int n = sizeof(items) / sizeof(items[0]);
    float maxValue = fractionalKnapsack(W, items, n);
    printf("%.2f\n", maxValue);
    return 0;
}

A 220.00

B 240.00

C 180.00

D 200.00

💡 Hint

Sort items by value-to-weight ratio and pick items until the knapsack is full.

The code sorts items by their value-to-weight ratio in descending order. Then it adds whole items until the knapsack is full. For the last item, it adds the fractional part that fits.

Items sorted by ratio: (60/10=6), (100/20=5), (120/30=4). Total capacity is 50.

Pick item 1 fully (weight 10, value 60), remaining capacity 40.

Pick item 2 fully (weight 20, value 100), remaining capacity 20.

Pick 20/30 fraction of item 3: value = 4 * 20 = 80.

Total value = 60 + 100 + 80 = 240.

🧠 Conceptual

intermediate

Understanding Fractional Knapsack Strategy

Why does the fractional knapsack problem use the value-to-weight ratio to decide which items to pick first?

A Because it maximizes the value gained per unit weight, ensuring the knapsack is filled with the most valuable fractions first.

B Because it minimizes the total weight of items, allowing more items to fit regardless of value.

C Because it sorts items alphabetically by name to maintain order.

D Because it picks items randomly to avoid bias.

💡 Hint

Think about how to get the most value for the limited capacity.

The value-to-weight ratio shows how much value each unit of weight contributes. Picking items with the highest ratio first ensures the knapsack holds the most valuable combination.

🔧 Debug

advanced

Identify the Bug in Fractional Knapsack Sorting

What is the bug in the following sorting code snippet used in fractional knapsack implementation?

DSA C

for (i = 0; i < n - 1; i++) {
    for (int j = i + 1; j < n; j++) {
        if (ratio[i] > ratio[j]) {
            float temp = ratio[i]; ratio[i] = ratio[j]; ratio[j] = temp;
            Item tempItem = items[i]; items[i] = items[j]; items[j] = tempItem;
        }
    }
}

A The swap of items is missing, only ratio array is swapped.

B The loop indices are incorrect and cause out-of-bounds access.

C The comparison should be ratio[i] < ratio[j] to sort in descending order of ratio.

D The code uses bubble sort which is inefficient and should be replaced.

💡 Hint

Check if the sorting order matches the problem requirement.

The fractional knapsack requires sorting items by descending value-to-weight ratio. The code uses ratio[i] > ratio[j], which sorts ascending. It should be ratio[i] < ratio[j] to sort descending.

❓ Predict Output

advanced

Output of Fractional Knapsack with Zero Capacity

What is the output of this C code when the knapsack capacity is zero?

DSA C

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

float fractionalKnapsack(int W, Item items[], int n) {
    float totalValue = 0.0;
    int i, curWeight = 0;
    float ratio[n];

    for (i = 0; i < n; i++) {
        ratio[i] = (float)items[i].value / items[i].weight;
    }

    for (i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            if (ratio[i] < ratio[j]) {
                float temp = ratio[i]; ratio[i] = ratio[j]; ratio[j] = temp;
                Item tempItem = items[i]; items[i] = items[j]; items[j] = tempItem;
            }
        }
    }

    for (i = 0; i < n; i++) {
        if (curWeight + items[i].weight <= W) {
            curWeight += items[i].weight;
            totalValue += items[i].value;
        } else {
            int remain = W - curWeight;
            totalValue += ratio[i] * remain;
            break;
        }
    }
    return totalValue;
}

#include <stdio.h>
int main() {
    Item items[] = {{60, 10}, {100, 20}, {120, 30}};
    int W = 0;
    int n = sizeof(items) / sizeof(items[0]);
    float maxValue = fractionalKnapsack(W, items, n);
    printf("%.2f\n", maxValue);
    return 0;
}

A 120.00

B 60.00

C 100.00

D 0.00

💡 Hint

If capacity is zero, no items can be added.

Since the knapsack capacity is zero, no weight can be added. The total value remains zero.

🧠 Conceptual

expert

Why Fractional Knapsack is Greedy but 0/1 Knapsack is Not

Why does the fractional knapsack problem allow a greedy approach to find the optimal solution, but the 0/1 knapsack problem does not?

A Because fractional knapsack allows splitting items, so picking the best ratio first always leads to optimal, while 0/1 knapsack requires considering combinations.

B Because 0/1 knapsack sorts items by weight only, which is not optimal.

C Because fractional knapsack uses dynamic programming internally, unlike 0/1 knapsack.

D Because 0/1 knapsack has fewer items, so greedy is unnecessary.

💡 Hint

Think about the difference between splitting items and taking whole items only.

Fractional knapsack allows taking parts of items, so choosing the highest value-to-weight ratio first always leads to the best total value. 0/1 knapsack requires whole items only, so combinations must be checked to find the best set.