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 filling a jar with different types of honey. Each honey has a price per spoon. You want to fill the jar with the most expensive honey first, even if you only take a spoonful of some honey.

Items: [value/weight ratio]
Knapsack capacity: 50

Items:
[Item1: 60/10=6] -> [Item2: 100/20=5] -> [Item3: 120/30=4]
Knapsack: empty ↑ capacity=50

Dry Run Walkthrough

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

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

Step 1: Sort items by value/weight ratio descending

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

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

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

Knapsack: 10/50 filled, total value=60

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

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

Knapsack: 30/50 filled, total value=160

Why: Item2 fits fully, continue taking whole items

Step 4: Take fraction of Item3 to fill remaining capacity (20/30 fraction)

Knapsack: 50/50 filled, total value=160 + (120 * 20/30) = 240

Why: Only partial Item3 fits, take fraction to fill knapsack fully

Result:

Knapsack full: 50/50 weight, total value = 240

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

class Item
{
    public int Value { get; set; }
    public int Weight { get; set; }
    public double Ratio => (double)Value / Weight;

    public Item(int value, int weight)
    {
        Value = value;
        Weight = weight;
    }
}

class FractionalKnapsack
{
    public static double GetMaxValue(List<Item> items, int capacity)
    {
        // Sort items by value/weight ratio descending
        items.Sort((a, b) => b.Ratio.CompareTo(a.Ratio));

        double totalValue = 0;
        int remainingCapacity = capacity;

        foreach (var item in items)
        {
            if (remainingCapacity == 0)
                break; // knapsack full

            if (item.Weight <= remainingCapacity)
            {
                // Take whole item
                totalValue += item.Value;
                remainingCapacity -= item.Weight;
            }
            else
            {
                // Take fraction of item
                double fraction = (double)remainingCapacity / item.Weight;
                totalValue += item.Value * fraction;
                remainingCapacity = 0; // knapsack full
            }
        }

        return totalValue;
    }

    static void Main()
    {
        var items = new List<Item>
        {
            new Item(60, 10),
            new Item(100, 20),
            new Item(120, 30)
        };

        int capacity = 50;
        double maxValue = GetMaxValue(items, capacity);
        Console.WriteLine($"Maximum value in knapsack = {maxValue}");
    }
}

items.Sort((a, b) => b.Ratio.CompareTo(a.Ratio));

Sort items by descending value/weight ratio to prioritize best value

if (remainingCapacity == 0) break;

Stop if knapsack is full

if (item.Weight <= remainingCapacity)

Check if whole item fits in remaining capacity

totalValue += item.Value; remainingCapacity -= item.Weight;

Add full item value and reduce capacity

double fraction = (double)remainingCapacity / item.Weight; totalValue += item.Value * fraction; remainingCapacity = 0;

Add fractional item value to fill knapsack exactly

Output

Maximum value in knapsack = 240

Complexity Analysis

Time: O(n log n) because we sort n items by their value/weight ratio

Space: O(n) for storing the list of items

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

Edge Cases

Empty list of items

Returns 0 value since no items to take

DSA C#

foreach (var item in items) { if (remainingCapacity == 0) break; }

Knapsack capacity zero

Returns 0 value immediately

DSA C#

if (remainingCapacity == 0) break;

Item weight larger than capacity

Takes fraction of that item to fill knapsack

DSA C#

else { double fraction = (double)remainingCapacity / item.Weight; ... }

When to Use This Pattern

When you can take parts of items to maximize value and need the best value per weight, use the fractional knapsack greedy approach.

Common Mistakes

Mistake: Trying to take whole items only and ignoring fractions
Fix: Implement fraction calculation to fill remaining capacity exactly

Mistake: Not sorting items by value/weight ratio before selection
Fix: Sort items descending by ratio to ensure greedy correctness

Summary

Find the maximum total value by taking whole or fractional items within capacity.

Use when partial items can be taken and you want to maximize value efficiently.

Sort items by value per weight and take as much as possible from highest ratio first.

Practice

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

easy

A. Maximize number of items regardless of weight

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

C. Minimize total weight by selecting whole items only

D. Select items randomly without considering value or weight

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 states maximizing total value by taking fractions within weight limit.

3. Final Answer:

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

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-to-weight ratio

2. Which C# syntax correctly declares a class named Item with public fields weight and value?

easy

A. class Item { public int weight; public int value; }

B. class Item { int weight; int value; }

C. public Item { int weight; int value; }

D. class Item { public weight; public value; }

Solution

1. Step 1: Check class declaration syntax

   In C#, class fields must have type and access modifier for public fields.

2. Step 2: Validate each option

   class Item { public int weight; public int value; } correctly declares public int fields. class Item { int weight; int value; } lacks access modifier. public Item { int weight; int value; } misses class keyword. class Item { public weight; public value; } misses types.

3. Final Answer:

   class Item { public int weight; public int value; } -> Option A

4. Quick Check:

   Correct class syntax = class Item { public int weight; public int value; } [OK]

Hint: Public fields need type and access modifier [OK]

Common Mistakes:

• Omitting access modifiers
• Missing data types
• Incorrect class keyword usage

3. What is the output of this C# code snippet for fractional knapsack?

var items = new[] {
  new Item { weight = 10, value = 60 },
  new Item { weight = 20, value = 100 },
  new Item { weight = 30, value = 120 }
};
int capacity = 50;
double maxValue = 0;
Array.Sort(items, (a, b) => (b.value / (double)b.weight).CompareTo(a.value / (double)a.weight));
int remaining = capacity;
foreach (var item in items) {
  if (item.weight <= remaining) {
    maxValue += item.value;
    remaining -= item.weight;
  } else {
    maxValue += item.value * (remaining / (double)item.weight);
    break;
  }
}
Console.WriteLine(Math.Round(maxValue, 2));

medium

A. 200.00

B. 220.00

C. 180.00

D. 240.00

Solution

1. Step 1: Sort items by value/weight ratio

   Ratios: Item1=6, Item2=5, Item3=4. Sorted order: Item1, Item2, Item3.

2. Step 2: Add items until capacity 50

   Take Item1 fully (weight 10, value 60), remaining=40. Take Item2 fully (weight 20, value 100), remaining=20. Take 20/30 fraction of Item3: value = 120 * (20/30) = 80.

3. Step 3: Calculate total value

   Total = 60 + 100 + 80 = 240. Rounded to 240.00.

4. Final Answer:

   240.00 -> Option D

5. Quick Check:

   Sum values with fractions = 240.00 [OK]

Hint: Sort by value/weight, take full then fraction [OK]

Common Mistakes:

• Not sorting by value/weight ratio
• Taking items without fraction
• Incorrect fraction calculation

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

int capacity = 50;
var items = new List<Item> {
  new Item { weight = 10, value = 60 },
  new Item { weight = 20, value = 100 },
  new Item { weight = 30, value = 120 }
};
items.Sort((a, b) => (a.value / a.weight).CompareTo(b.value / b.weight));
double maxValue = 0;
int remaining = capacity;
foreach (var item in items) {
  if (item.weight <= remaining) {
    maxValue += item.value;
    remaining -= item.weight;
  } else {
    maxValue += item.value * (remaining / item.weight);
    break;
  }
}
Console.WriteLine(maxValue);

medium

A. Sorting order is ascending instead of descending

B. Missing check for zero weight items

C. Integer division causes incorrect ratio calculation

D. Using List instead of array causes error

Solution

1. Step 1: Analyze sorting comparator

   The comparator uses integer division (a.value / a.weight) which truncates decimals, causing wrong ratios.

2. Step 2: Impact on sorting and calculation

   Integer division leads to incorrect sorting order and wrong maxValue calculation.

3. Final Answer:

   Integer division causes incorrect ratio calculation -> Option C

4. Quick Check:

   Use double division for correct ratios [OK]

Hint: Use double division for ratios, not integer division [OK]

Common Mistakes:

• Sorting ascending instead of descending
• Ignoring integer division truncation
• Assuming List causes error

5. Given items with weights and values: [(5, 30), (10, 40), (15, 45)], and knapsack capacity 20, what is the maximum value achievable using fractional knapsack?

hard

A. 85

B. 75

C. 80

D. 70

Solution

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

   Ratios: (5,30)=6, (10,40)=4, (15,45)=3. Sorted order: (5,30), (10,40), (15,45).

2. Step 2: Fill knapsack capacity 20

   Take full (5,30), remaining=15, value=30. Take full (10,40), remaining=5, value=70. Take fraction of (15,45): 5/15=1/3 fraction, value=45*(1/3)=15.

3. Step 3: Calculate total value

   Total value = 30 + 40 + 15 = 85.

4. Final Answer:

   85 -> Option A

5. Quick Check:

   Sum with fractions = 85 [OK]

Hint: Sort by ratio, take full items first, then fraction [OK]

Common Mistakes:

• Not sorting by value/weight ratio
• Taking items without fraction
• Incorrect fraction calculation