Fractional Knapsack Problem in DSA C - Execution Trace

Concept Flow - Fractional Knapsack Problem

Start with empty knapsack

↓

Sort items by value/weight ratio

↓

For each item in sorted order

↓

Can full item fit?

No→Take fraction to fill knapsack

|Yes↓

Add full item to knapsack

↓

Knapsack full?

No→Next item

Yes↓

Done

We sort items by value per weight, then add as much as possible from each until the knapsack is full.

Execution Sample

DSA C

items = [(60, 10), (100, 20), (120, 30)]; capacity = 50;
// Sort by value/weight ratio
// Take items fully or fractionally until capacity fills.

This code picks items or fractions to maximize value within capacity.

Execution Table

Step	Operation	Item Taken	Weight Added	Value Added	Remaining Capacity	Knapsack State (weight:value)
1	Sort items by value/weight	-	-	-	50	-
2	Take full item	(60,10)	10	60	40	10:60
3	Take full item	(100,20)	20	100	20	30:160
4	Take fraction of item	(120,30)	20 (fraction)	80	0	50:240
5	Knapsack full	-	-	-	0	50:240

💡 Knapsack capacity reached 0, no more items can be added.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
Remaining Capacity	50	40	20	0	0
Total Value	0	60	160	240	240
Knapsack Weight	0	10	30	50	50

Key Moments - 3 Insights

Why do we sort items by value/weight ratio before picking?

Sorting ensures we pick items giving the most value per weight first, maximizing total value as shown in Step 1 of execution_table.

Why do we take only a fraction of the last item?

When the remaining capacity is less than the item's weight (Step 4), we take only the fraction that fits to fill the knapsack exactly.

What happens when the knapsack capacity reaches zero?

The process stops immediately (Step 5) because no more weight can be added, ensuring we don't exceed capacity.

Visual Quiz - 3 Questions

Look at the execution_table, what is the remaining capacity after Step 3?

A 20

B 30

C 40

D 10

💡 Hint

Check the 'Remaining Capacity' column at Step 3 in execution_table.

At which step do we add a fractional part of an item?

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Look for 'Take fraction of item' in the Operation column of execution_table.

If the knapsack capacity was 60 instead of 50, what would change in the knapsack state after Step 4?

A Knapsack weight would be 50

B Knapsack weight would be 60

C Knapsack value would be 240

D Knapsack value would be less than 240

💡 Hint

Check how weight added accumulates in variable_tracker and execution_table.

Concept Snapshot

Fractional Knapsack Problem:
- Sort items by value/weight ratio descending
- Pick full items while capacity allows
- Take fraction of next item if needed
- Stop when capacity is full
- Maximizes total value with fractional items allowed

Full Transcript

The Fractional Knapsack Problem involves filling a knapsack with items to maximize value without exceeding capacity. We first sort items by their value-to-weight ratio to prioritize the most valuable per weight. Then, we add items fully if they fit, or fractionally if only part fits, until the knapsack is full. This approach ensures maximum total value. The execution table shows each step: sorting, adding full items, adding a fraction, and stopping when full. Variables like remaining capacity and total value update accordingly. Key points include why sorting is essential, why fractions are taken, and stopping when full. The quiz checks understanding of capacity changes and fractional addition.

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