Fractional Knapsack Problem in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Fractional Knapsack Calculation

What is the output of the following C# code that calculates the maximum value for a fractional knapsack problem?

DSA C#

using System;

class Item {
    public int value, weight;
    public Item(int v, int w) { value = v; weight = w; }
}

class Program {
    static double FractionalKnapsack(Item[] items, int capacity) {
        Array.Sort(items, (a, b) => (b.value / (double)b.weight).CompareTo(a.value / (double)a.weight));
        double totalValue = 0.0;
        int remaining = capacity;
        foreach (var item in items) {
            if (item.weight <= remaining) {
                totalValue += item.value;
                remaining -= item.weight;
            } else {
                totalValue += item.value * (remaining / (double)item.weight);
                break;
            }
        }
        return totalValue;
    }

    static void Main() {
        Item[] items = { new Item(60, 10), new Item(100, 20), new Item(120, 30) };
        int capacity = 50;
        Console.WriteLine(FractionalKnapsack(items, capacity));
    }
}

A 200

B 220

C 240

D 180

💡 Hint

Sort items by value-to-weight ratio and add as much as possible until capacity is full.

The items are sorted by value/weight ratio: (60/10=6), (100/20=5), (120/30=4). We take all of the first two items (10+20=30 weight, 60+100=160 value), then 20 weight from the last item (20/30 fraction), adding 120*(20/30)=80 value. Total = 160+80=240.

🧠 Conceptual

intermediate

Key Idea Behind Fractional Knapsack

Which of the following best describes the key idea behind the fractional knapsack problem?

A Items are chosen randomly until capacity is full.

B Items must be taken whole or not at all, no breaking allowed.

C Only the lightest items are chosen regardless of value.

D Items can be broken into smaller parts to maximize total value within capacity.

💡 Hint

Think about how fractional knapsack differs from 0/1 knapsack.

Fractional knapsack allows breaking items into smaller parts to fill the knapsack optimally, unlike 0/1 knapsack where items are taken whole.

🔧 Debug

advanced

Identify the Error in Fractional Knapsack Code

What error will the following C# code produce when run?

DSA C#

using System;

class Item {
    public int value, weight;
    public Item(int v, int w) { value = v; weight = w; }
}

class Program {
    static double FractionalKnapsack(Item[] items, int capacity) {
        Array.Sort(items, (a, b) => (a.value / a.weight).CompareTo(b.value / b.weight));
        double totalValue = 0.0;
        int remaining = capacity;
        foreach (var item in items) {
            if (item.weight <= remaining) {
                totalValue += item.value;
                remaining -= item.weight;
            } else {
                totalValue += item.value * (remaining / (double)item.weight);
                break;
            }
        }
        return totalValue;
    }

    static void Main() {
        Item[] items = { new Item(60, 10), new Item(100, 20), new Item(120, 30) };
        int capacity = 50;
        Console.WriteLine(FractionalKnapsack(items, capacity));
    }
}

A Runtime error: division by zero

B Incorrect output less than expected maximum value

C Compile-time error due to invalid lambda expression

D Output is 240.0

💡 Hint

Check how sorting compares value/weight ratios.

The sorting compares integer division (value/weight) which truncates decimals, causing incorrect order and thus incorrect total value.

🚀 Application

advanced

Choosing Items for Fractional Knapsack

Given items with values and weights: (40, 2), (100, 20), (50, 10), and capacity 15, which items and fractions will maximize the knapsack value?

A Take full (40,2), 65% of (100,20), no (50,10)

B Take full (100,20) only

C Take full (40,2), full (50,10), and 15% of (100,20)

D Take full (40,2), full (100,20), no (50,10)

💡 Hint

Sort by value/weight ratio and fill capacity greedily.

Ratios: 40/2=20, 100/20=5, 50/10=5. Take full (40,2), then 13 weight from (100,20) (65%), total weight 15.

🧠 Conceptual

expert

Why Greedy Works for Fractional Knapsack but Not 0/1 Knapsack

Why does the greedy approach guarantee an optimal solution for fractional knapsack but not for 0/1 knapsack?

A Because fractional knapsack allows partial items, making the problem continuous and greedy optimal.

B Because 0/1 knapsack has fewer items to choose from.

C Because greedy always works for all knapsack problems.

D Because fractional knapsack ignores item weights.

💡 Hint

Consider problem constraints and solution space.

Fractional knapsack is a continuous problem allowing partial items, so greedy picking by ratio is optimal. 0/1 knapsack is discrete, requiring dynamic programming.

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