Fractional Knapsack Problem in DSA C++ - Execution Trace

Concept Flow - Fractional Knapsack Problem

Start: Given items with weights and values

↓

Calculate value/weight ratio for each item

↓

Sort items by ratio descending

↓

Initialize total_weight = 0, total_value = 0

↓

For each item in sorted list

↓

If item fits fully: Add full weight and value

↓

Else: Add fractional part to fill knapsack

↓

Stop when knapsack is full or all items processed

↓

Return total_value as max profit

The flow shows how items are sorted by value per weight and added fully or partially to maximize total value within capacity.

Execution Sample

DSA C++

struct Item {
  double value, weight;
};

// Fractional Knapsack function
// Returns max value for capacity W

double fractionalKnapsack(Item items[], int n, double W) {
  // ... implementation ...
}

This code calculates the maximum value that fits in a knapsack of capacity W by taking full or fractional parts of items.

Execution Table

Step	Operation	Item Chosen (value, weight)	Fraction Taken	Weight Added	Value Added	Total Weight	Total Value	Knapsack State
1	Calculate ratio	(60, 10)	1.0	0	0	0	0	Ratios: 6.0, 5.0, 4.0
2	Calculate ratio	(100, 20)	1.0	0	0	0	0	Ratios: 6.0, 5.0, 4.0
3	Calculate ratio	(120, 30)	1.0	0	0	0	0	Ratios: 6.0, 5.0, 4.0
4	Sort items by ratio	Sorted order: (60,10), (100,20), (120,30)	1.0	0	0	0	0	Sorted by ratio descending
5	Take full item	(60, 10)	1.0	10	60	10	60	Knapsack: 10/50 weight, 60 value
6	Take full item	(100, 20)	1.0	20	100	30	160	Knapsack: 30/50 weight, 160 value
7	Take fractional item	(120, 30)	0.6667	20	80	50	240	Knapsack full: 50/50 weight, 240 value
8	Stop	No more capacity	0	0	0	50	240	Knapsack full, stop

💡 Knapsack capacity reached at step 7 with total weight 50 equal to capacity.

Variable Tracker

Variable	Start	After Step 5	After Step 6	After Step 7	Final
total_weight	0	10	30	50	50
total_value	0	60	160	240	240
fraction_taken (last item)	0	0	0	0.6667	0.6667

Key Moments - 3 Insights

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

At step 7 in the execution_table, the remaining capacity is 20 but the item weight is 30, so only 20/30 = 0.6667 fraction is taken to fill the knapsack exactly.

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

Sorting by ratio ensures we pick items that give the most value per unit weight first, maximizing total value as shown in step 4.

What happens if the knapsack capacity is larger than total weights of all items?

The loop would take all items fully without fractions, and total_value would be sum of all values, stopping after all items are added.

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what is the total weight in the knapsack?

A 30

B 20

C 10

D 50

💡 Hint

Check the 'Total Weight' column at step 6 in the execution_table.

At which step does the knapsack become full?

A Step 5

B Step 6

C Step 7

D Step 8

💡 Hint

Look for when 'Total Weight' equals knapsack capacity in the execution_table.

If the item (120, 30) had a higher ratio than (100, 20), how would the order change?

A It would be chosen last

B It would be chosen first

C Order stays the same

D It would be skipped

💡 Hint

Refer to step 4 where items are sorted by ratio descending.

Concept Snapshot

Fractional Knapsack Problem:
- Calculate value/weight ratio for each item
- Sort items by descending ratio
- Add items fully while capacity allows
- Add fractional part of next item if needed
- Stop when knapsack is full
- Maximizes total value within capacity

Full Transcript

The Fractional Knapsack Problem involves selecting items with given weights and values to maximize total value in a knapsack with limited capacity. We first calculate the value per weight ratio for each item, then sort items by this ratio in descending order. We add items fully to the knapsack while there is enough capacity. When the next item cannot fit fully, we add the fractional part that fits exactly. This process continues until the knapsack is full or all items are processed. The final total value is the maximum achievable. The execution table shows step-by-step how items are chosen, fractions taken, and the knapsack state updates.

Practice

1. What is the main goal of the Fractional Knapsack Problem?

easy

A. Maximize total value by taking fractions of items within weight limit

B. Maximize total value by taking whole items only

C. Minimize total weight of items selected

D. Find the minimum number of items to fill the knapsack

Solution

1. Step 1: Understand problem goal

   The fractional knapsack problem allows taking parts of items to maximize value within a weight limit.

2. Step 2: Compare options

   Maximize total value by taking fractions of items within weight limit correctly states maximizing value by fractions; others are about whole items or minimizing weight, which are incorrect.

3. Final Answer:

   Maximize total value by taking fractions of items within weight limit -> Option A

4. Quick Check:

   Fractional knapsack = maximize value with fractions [OK]

Hint: Fractional knapsack allows partial items for max value [OK]

Common Mistakes:

• Confusing fractional knapsack with 0/1 knapsack
• Thinking only whole items can be taken
• Assuming problem minimizes weight

2. Which of the following C++ code snippets correctly sorts items by value-to-weight ratio in descending order for fractional knapsack?

easy

A. std::sort(items.begin(), items.end(), [](auto &a, auto &b) { return a.weight > b.weight; });

B. std::sort(items.begin(), items.end(), [](auto &a, auto &b) { return (a.value / a.weight) > (b.value / b.weight); });

C. std::sort(items.begin(), items.end(), [](auto &a, auto &b) { return a.value < b.value; });

D. std::sort(items.begin(), items.end(), [](auto &a, auto &b) { return (a.weight / a.value) > (b.weight / b.value); });

Solution

1. Step 1: Identify correct sorting criteria

   We must sort by value-to-weight ratio descending: (value/weight) high to low.

2. Step 2: Check each option

   std::sort(items.begin(), items.end(), [](auto &a, auto &b) { return (a.value / a.weight) > (b.value / b.weight); }); sorts by (value/weight) descending correctly. Others sort by wrong ratio or by value or weight alone.

3. Final Answer:

   std::sort(items.begin(), items.end(), [](auto &a, auto &b) { return (a.value / a.weight) > (b.value / b.weight); }); -> Option B

4. Quick Check:

   Sort by value/weight descending = std::sort(items.begin(), items.end(), [](auto &a, auto &b) { return (a.value / a.weight) > (b.value / b.weight); }); [OK]

Hint: Sort by value/weight ratio descending for greedy pick [OK]

Common Mistakes:

• Sorting by weight/value instead of value/weight
• Sorting ascending instead of descending
• Sorting by value or weight alone

3. What is the output of the following C++ code snippet for fractional knapsack?

struct Item { int value; int weight; };
std::vector<Item> items = {{60, 10}, {100, 20}, {120, 30}};
int W = 50;
// Assume items sorted by value/weight descending
float totalValue = 0;
int capacity = W;
for (auto &item : items) {
  if (item.weight <= capacity) {
    capacity -= item.weight;
    totalValue += item.value;
  } else {
    totalValue += item.value * ((float)capacity / item.weight);
    break;
  }
}
std::cout << totalValue << std::endl;

medium

A. 180

B. 220

C. 200

D. 240

Solution

1. Step 1: Calculate value/weight ratios and sort

   Ratios: 60/10=6, 100/20=5, 120/30=4. Sorted order: {60,10}, {100,20}, {120,30}.

2. Step 2: Pick items greedily until capacity 50

   Take first item fully: capacity=50-10=40, totalValue=60. Take second item fully: capacity=40-20=20, totalValue=60+100=160. Take third item fraction: fraction=20/30=2/3, value=120*(2/3)=80. Total value=160+80=240.

3. Final Answer:

   240 -> Option D

4. Quick Check:

   Sum values with fractions = 240 [OK]

Hint: Pick full items then fraction of next to fill capacity [OK]

Common Mistakes:

• Not sorting items by value/weight ratio
• Taking items in wrong order
• Incorrect fraction calculation

4. Identify the bug in this fractional knapsack code snippet:

float fractionalKnapsack(int W, std::vector<Item> &items) {
  std::sort(items.begin(), items.end(), [](auto &a, auto &b) {
    return (a.value / a.weight) > (b.value / b.weight);
  });
  float totalValue = 0;
  int capacity = W;
  for (auto &item : items) {
    if (item.weight < capacity) {
      capacity -= item.weight;
      totalValue += item.value;
    } else {
      totalValue += item.value * ((float)capacity / item.weight);
      break;
    }
  }
  return totalValue;
}

medium

A. Should use <= instead of < in if condition to include full item when equal

B. Sorting comparator divides integers causing integer division error

C. Capacity variable should be float, not int

D. Missing return statement at end of function

Solution

1. Step 1: Analyze if condition for full item inclusion

   The condition uses 'item.weight < capacity', so if weight equals capacity, it skips full inclusion and takes fraction.

2. Step 2: Correct condition to include full item when weight equals capacity

   Changing to 'item.weight <= capacity' allows taking full item if it fits exactly, which is correct behavior.

3. Final Answer:

   Should use <= instead of < in if condition to include full item when equal -> Option A

4. Quick Check:

   Use <= to include full item when weight equals capacity [OK]

Hint: Use <= to include full item when weight equals capacity [OK]

Common Mistakes:

• Using < instead of <= causing partial fraction unnecessarily
• Ignoring integer division in comparator (not an issue here)
• Wrong variable types for capacity

5. Given items with values and weights: {value: 40, weight: 2}, {value: 100, weight: 20}, {value: 50, weight: 10}, and knapsack capacity 25, what is the maximum value achievable using fractional knapsack?

hard

A. 160

B. 150

C. 155

D. 140

Solution

1. Step 1: Calculate value/weight ratios and sort items

   Ratios: - 40/2 = 20 - 100/20 = 5 - 50/10 = 5 Sorted order: {40,2}, {100,20}, {50,10} (40,2 first due to highest ratio)

2. Step 2: Pick items greedily until capacity 25

   Take first item fully: capacity=25-2=23, totalValue=40. Take second item fully: capacity=23-20=3, totalValue=40+100=140. Take third item fraction: fraction=3/10=0.3, value=50*0.3=15. Total value=140+15=155.

3. Step 3: Re-check sorting for tie in ratio

   Since second and third items have same ratio, order can be swapped. Try picking {40,2}, {50,10}, {100,20}: Take {40,2}: capacity=23, value=40 Take {50,10}: capacity=13, value=90 Take fraction of {100,20}: fraction=13/20=0.65, value=100*0.65=65 Total=40+50+65=155 (same)

4. Final Answer:

   155 -> Option C

5. Quick Check:

   Pick highest ratio items fully, fraction last = 155 [OK]

Hint: Sort by ratio, pick full items, fraction last to fill capacity [OK]

Common Mistakes:

• Not sorting by value/weight ratio correctly
• Picking items in wrong order
• Ignoring fractional part calculation