Fractional Knapsack Problem in DSA C++

Mental Model

We want to fill a bag with items to get the most value, and we can take parts of items if needed.

Analogy: Imagine you have a backpack and different jars of honey. Each jar has a weight and sweetness. You want to fill your backpack with the sweetest honey possible, and you can pour some honey from a jar if it doesn't fit fully.

Items: [weight: 10, value: 60] -> [weight: 20, value: 100] -> [weight: 30, value: 120]
Knapsack capacity: 50
Knapsack: empty ↑

Dry Run Walkthrough

Input: items: [(weight=10, value=60), (weight=20, value=100), (weight=30, value=120)], capacity=50

Goal: Maximize total value in knapsack by taking whole or fractional parts of items

Step 1: Calculate value per weight for each item and sort items by this ratio descending

[Item1: 60/10=6] -> [Item2: 100/20=5] -> [Item3: 120/30=4]
Sorted: Item1 -> Item2 -> Item3

Why: We want to pick items with highest value per weight first to maximize total value

Step 2: Take full Item1 (weight 10) into knapsack

Knapsack: 10/50 weight used, value=60 ↑

Why: Item1 fits fully, so take it all to maximize value

Step 3: Take full Item2 (weight 20) into knapsack

Knapsack: 30/50 weight used, value=160 ↑

Why: Item2 fits fully, so take it all to maximize value

Step 4: Take fractional part of Item3 to fill remaining capacity (20 out of 30 weight)

Knapsack: 50/50 weight used, value=160 + (20/30)*120 = 240 ↑

Why: Only part of Item3 fits, so take fraction to fill knapsack fully

Result:

Knapsack full: total weight 50 -> total value 240

Annotated Code

DSA C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Item {
    int weight;
    int value;
    double value_per_weight;
};

bool cmp(Item a, Item b) {
    return a.value_per_weight > b.value_per_weight;
}

double fractionalKnapsack(int capacity, vector<Item>& items) {
    for (auto& item : items) {
        item.value_per_weight = (double)item.value / item.weight; // calculate ratio
    }
    sort(items.begin(), items.end(), cmp); // sort by ratio descending

    double total_value = 0.0;
    int current_weight = 0;

    for (auto& item : items) {
        if (current_weight + item.weight <= capacity) {
            current_weight += item.weight; // add full item weight
            total_value += item.value; // add full item value
        } else {
            int remain = capacity - current_weight;
            total_value += item.value_per_weight * remain; // add fractional value
            break; // knapsack full
        }
    }
    return total_value;
}

int main() {
    vector<Item> items = {{10, 60, 0}, {20, 100, 0}, {30, 120, 0}};
    int capacity = 50;
    double max_value = fractionalKnapsack(capacity, items);
    cout << "Maximum value in knapsack = " << max_value << "\n";
    return 0;
}

item.value_per_weight = (double)item.value / item.weight; // calculate ratio

compute value per weight ratio for each item to prioritize

sort(items.begin(), items.end(), cmp); // sort by ratio descending

sort items so we pick highest value per weight first

if (current_weight + item.weight <= capacity) {

check if full item fits in knapsack

current_weight += item.weight; // add full item weight

add full item weight to knapsack

total_value += item.value; // add full item value

add full item value to total

int remain = capacity - current_weight;

calculate remaining capacity for fractional item

total_value += item.value_per_weight * remain; // add fractional value

add fractional value proportional to remaining capacity

break; // knapsack full

stop as knapsack is full

Output

Maximum value in knapsack = 240

Complexity Analysis

Time: O(n log n) because we sort the items by value per weight ratio

Space: O(n) for storing items and their ratios

vs Alternative: Compared to 0/1 knapsack which is O(n*capacity), fractional knapsack is faster due to greedy sorting

Edge Cases

Empty items list

Returns 0 value as no items to take

DSA C++

for (auto& item : items) { ... } handles empty vector gracefully

Capacity zero

Returns 0 value as knapsack cannot hold anything

DSA C++

if (current_weight + item.weight <= capacity) condition prevents adding any item

Item with zero weight

Avoid division by zero by not having zero weight items (assumed input validation)

DSA C++

item.value_per_weight = (double)item.value / item.weight; // assumes weight > 0

When to Use This Pattern

When you can take fractions of items to maximize value under weight limit, use the fractional knapsack greedy approach sorting by value per weight.

Common Mistakes

Mistake: Not sorting items by value per weight ratio before picking
Fix: Always compute and sort items by value per weight ratio descending before selection

Mistake: Trying to take fractional part without checking remaining capacity
Fix: Calculate remaining capacity and take fraction accordingly, then stop

Summary

It finds the maximum value by taking whole or fractional parts of items to fill the knapsack.

Use it when you can split items and want to maximize value under a weight limit.

The key is to pick items with the highest value per weight first, taking fractions if needed.

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