Fractional Knapsack Problem in DSA C++ - Time & Space Complexity

Time Complexity: Fractional Knapsack Problem

O(n log n)

Understanding Time Complexity

We want to understand how the time needed to solve the Fractional Knapsack Problem changes as the number of items grows.

Specifically, we ask: how does the work increase when we have more items to choose from?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

struct Item {
    int value, weight;
};

bool cmp(Item a, Item b) {
    return (double)a.value / a.weight > (double)b.value / b.weight;
}

double fractionalKnapsack(int W, Item arr[], int n) {
    sort(arr, arr + n, cmp);
    double totalValue = 0.0;
    for (int i = 0; i < n; i++) {
        if (arr[i].weight <= W) {
            W -= arr[i].weight;
            totalValue += arr[i].value;
        } else {
            totalValue += arr[i].value * ((double)W / arr[i].weight);
            break;
        }
    }
    return totalValue;
}
    

This code sorts items by value per weight and then picks as much as possible from the best items until the knapsack is full.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Sorting the array of items by value-to-weight ratio.
• How many times: Sorting takes multiple comparisons, roughly proportional to n log n times for n items.
• Secondary operation: One loop through all items to fill the knapsack, running n times.

How Execution Grows With Input

As the number of items increases, sorting takes more time, growing faster than just going through the list once.

Input Size (n)	Approx. Operations
10	About 30 to 40 operations (sorting + loop)
100	About 700 to 800 operations (sorting dominates)
1000	About 10,000 to 12,000 operations (sorting dominates)

Pattern observation: The sorting step grows faster than the simple loop, so total work grows roughly like n log n.

Final Time Complexity

Time Complexity: O(n log n)

This means the time needed grows a bit faster than the number of items, mainly because of sorting.

Common Mistake

[X] Wrong: "The fractional knapsack runs in linear time because we just pick items once."

[OK] Correct: Sorting the items by value per weight takes more time than just picking; this sorting step is the main cost.

Interview Connect

Understanding this time complexity helps you explain why sorting is important before making greedy choices, a key skill in many algorithm problems.

Self-Check

"What if the items were already sorted by value per weight? How would the time complexity change?"

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