Fractional Knapsack Problem in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the Fractional Knapsack Problem?

It is a problem where you have a knapsack with a weight limit and items with weights and values. You can take fractions of items to maximize the total value without exceeding the weight limit.

beginner

Why can we take fractions of items in the Fractional Knapsack Problem but not in the 0/1 Knapsack Problem?

Because the problem allows breaking items into smaller parts, so you can take any fraction of an item. In 0/1 Knapsack, items are indivisible and must be taken whole or not at all.

beginner

What is the main strategy used to solve the Fractional Knapsack Problem?

Use a greedy approach: sort items by value per weight (value/weight) in descending order, then take as much as possible from the highest ratio items until the knapsack is full.

beginner

How do you calculate the value per weight ratio for an item?

Divide the item's value by its weight: ratio = value / weight. This ratio helps decide which items to pick first.

intermediate

What is the time complexity of the Fractional Knapsack Problem solution using sorting?

The time complexity is O(n log n) because sorting the items by their value/weight ratio takes O(n log n), and then selecting items is O(n).

In the Fractional Knapsack Problem, what determines the order in which items are chosen?

A Value of items

B Weight of items

C Value per weight ratio of items

D Number of items

Items are chosen based on their value per weight ratio, highest first, to maximize total value.

Can you take a part of an item in the Fractional Knapsack Problem?

A Yes, fractions of items are allowed

B No, items must be taken whole

C Only if the item is light

D Only if the item has high value

The problem allows taking any fraction of an item to fill the knapsack optimally.

What is the main difference between Fractional Knapsack and 0/1 Knapsack?

A Neither allow fractions

B 0/1 Knapsack allows fractions; Fractional does not

C Both allow fractions

D Fractional Knapsack allows breaking items; 0/1 does not

Fractional Knapsack allows taking parts of items, while 0/1 Knapsack requires whole items.

What is the first step in solving the Fractional Knapsack Problem?

A Pick the heaviest item

B Sort items by value per weight ratio

C Pick the item with highest value

D Pick items randomly

Sorting by value per weight ratio helps pick the most valuable items first.

What is the time complexity of the Fractional Knapsack solution?

A O(n log n)

B O(n^2)

C O(n)

D O(log n)

Sorting the items takes O(n log n), which dominates the time complexity.

Explain how the greedy approach works in the Fractional Knapsack Problem.

Think about choosing the most valuable parts first.

Describe the difference between Fractional Knapsack and 0/1 Knapsack problems.

Focus on item divisibility and solution methods.

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