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.

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