Fractional Knapsack Problem in DSA Java

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, even if you have to take only some honey from a jar.

Bag capacity: 50
Items:
[Weight: 10, Value: 60] -> [Weight: 20, Value: 100] -> [Weight: 30, Value: 120]
We can take full or partial items to maximize value.

Dry Run Walkthrough

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

Goal: Maximize total value in the bag by taking full or fractional parts of items without exceeding capacity

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

[Item1: 60/10=6.0] -> [Item2: 100/20=5.0] -> [Item3: 120/30=4.0]

Why: We want to pick items that give the most value per unit weight first

Step 2: Take full Item1 (weight 10) into bag, remaining capacity 40

Bag: 10/50 used, Value: 60

Why: Item1 fits fully and has highest value density

Step 3: Take full Item2 (weight 20) into bag, remaining capacity 20

Bag: 30/50 used, Value: 160

Why: Item2 fits fully and is next best value density

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

Bag: 50/50 used, Value: 160 + (120 * 20/30) = 240

Why: Only part of Item3 fits, so take fraction to maximize value

Result:

Bag full: 50/50 weight used
Total value: 240

Annotated Code

DSA Java

import java.util.*;

class Item {
    int weight, value;
    double ratio;
    Item(int w, int v) {
        weight = w;
        value = v;
        ratio = (double) v / w;
    }
}

public class FractionalKnapsack {
    public static double getMaxValue(Item[] items, int capacity) {
        Arrays.sort(items, (a, b) -> Double.compare(b.ratio, a.ratio));
        double totalValue = 0.0;
        int remainingCapacity = capacity;

        for (Item item : items) {
            if (remainingCapacity == 0) break;
            if (item.weight <= remainingCapacity) {
                totalValue += item.value;
                remainingCapacity -= item.weight;
            } else {
                totalValue += item.ratio * remainingCapacity;
                remainingCapacity = 0;
            }
        }
        return totalValue;
    }

    public static void main(String[] args) {
        Item[] items = {
            new Item(10, 60),
            new Item(20, 100),
            new Item(30, 120)
        };
        int capacity = 50;
        double maxValue = getMaxValue(items, capacity);
        System.out.println("Maximum value in bag: " + maxValue);
    }
}

Arrays.sort(items, (a, b) -> Double.compare(b.ratio, a.ratio));

Sort items by value per weight descending to prioritize best value density

for (Item item : items) {

Iterate over items in order of best value density

if (remainingCapacity == 0) break;

Stop if bag is full

if (item.weight <= remainingCapacity) {

If item fits fully, take whole item

totalValue += item.value;

Add full item value to total

remainingCapacity -= item.weight;

Reduce remaining capacity by item weight

else { totalValue += item.ratio * remainingCapacity; remainingCapacity = 0; }

Take fractional part of item to fill remaining capacity and stop

Output

Maximum value in bag: 240.0

Complexity Analysis

Time: O(n log n) because we sort n items by value density

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 and no dynamic programming

Edge Cases

Empty items array

Returns 0.0 value since no items to take

DSA Java

for (Item item : items) { if (remainingCapacity == 0) break; ...

Capacity zero

Returns 0.0 value immediately as bag cannot hold anything

DSA Java

if (remainingCapacity == 0) break;

Item with zero weight (invalid)

Division by zero avoided by problem constraints; if present, code may throw error

DSA Java

ratio calculation in Item constructor assumes weight > 0

When to Use This Pattern

When you need to maximize value with divisible items and limited capacity, use the fractional knapsack greedy approach by sorting items by value per weight.

Common Mistakes

Mistake: Not sorting items by value per weight ratio before selection
Fix: Always sort items descending by value/weight ratio to ensure optimal greedy choice

Mistake: Trying to take full items only, ignoring fractional parts
Fix: Allow fractional parts of items when capacity is insufficient for full item

Summary

It finds the maximum value that fits in a bag by taking full or fractional parts of items.

Use it when items can be divided and you want the best value for limited capacity.

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

Practice

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

easy

A. Select only whole items to maximize value

B. Minimize total weight of items selected

C. Sort items by weight only

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

Solution

1. Step 1: Understand problem objective

   The fractional knapsack problem allows taking parts of items to maximize total value without exceeding weight limit.

2. Step 2: Compare options

   Maximize total value by taking fractions of items within weight limit correctly states maximizing value by taking fractions. Others focus on minimizing weight or whole items only, which is incorrect.

3. Final Answer:

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

4. Quick Check:

   Goal = Maximize value with fractions [OK]

Hint: Remember: fractional means parts allowed, maximize value [OK]

Common Mistakes:

• Thinking only whole items can be taken
• Confusing weight minimization with value maximization
• Ignoring fractional parts possibility

2. Which Java code snippet correctly sorts items by value-to-weight ratio for the fractional knapsack?

easy

A. Arrays.sort(items, (a, b) -> Double.compare((double)b.value / b.weight, (double)a.value / a.weight));

B. Arrays.sort(items, (a, b) -> Double.compare(a.weight, b.weight));

C. Arrays.sort(items, (a, b) -> Integer.compare(a.value, b.value));

D. Arrays.sort(items, (a, b) -> a.value - b.value);

Solution

1. Step 1: Identify sorting criteria

   We must sort by value-to-weight ratio in descending order to pick best value fractions first.

2. Step 2: Check code correctness

   Arrays.sort(items, (a, b) -> Double.compare((double)b.value / b.weight, (double)a.value / a.weight)); sorts by ratio ((double)b.value/b.weight vs (double)a.value/a.weight) descending. Others sort by weight or value only, which is incorrect.

3. Final Answer:

   Arrays.sort(items, (a, b) -> Double.compare((double)b.value / b.weight, (double)a.value / a.weight)); -> Option A

4. Quick Check:

   Sort by ratio descending = Arrays.sort(items, (a, b) -> Double.compare((double)b.value / b.weight, (double)a.value / a.weight)); [OK]

Hint: Sort by value/weight descending for best fractions first [OK]

Common Mistakes:

• Sorting by weight or value alone
• Sorting in ascending order instead of descending
• Using integer division instead of double

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

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

Item[] items = {new Item(60, 10), new Item(100, 20), new Item(120, 30)};
int W = 50;
double maxValue = 0;
Arrays.sort(items, (a, b) -> Double.compare((double)b.value / b.weight, (double)a.value / a.weight));
int remaining = W;
for (Item item : items) {
  if (item.weight <= remaining) {
    maxValue += item.value;
    remaining -= item.weight;
  } else {
    maxValue += item.value * ((double)remaining / item.weight);
    break;
  }
}
System.out.println((int)maxValue);

medium

A. 180

B. 220

C. 240

D. 200

Solution

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

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

2. Step 2: Calculate max value with weight limit 50

   Take full (60,10): value=60, remaining=40
   Take full (100,20): value=160, remaining=20
   Take fraction of (120,30): fraction=20/30=2/3, value added=120*(2/3)=80
   Total value=60+100+80=240 but code casts to int after adding fractions, so 240.

3. Final Answer:

   240 -> Option C

4. Quick Check:

   Sum values with fractions = 240 [OK]

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

Common Mistakes:

• Not sorting by ratio correctly
• Taking items in wrong order
• Incorrect fraction calculation

4. Find the error in this Java code for fractional knapsack:

int maxValue = 0;
for (Item item : items) {
  if (item.weight <= W) {
    maxValue += item.value;
    W -= item.weight;
  } else {
    maxValue += item.value * (W / item.weight);
    break;
  }
}

medium

A. Loop condition should be item.weight <= W, not < W

B. Using integer division in fraction calculation causes wrong value

C. maxValue should be double, not int

D. No error, code is correct

Solution

1. Step 1: Analyze fraction calculation

   Expression (W / item.weight) uses integer division, truncating fraction to 0 or 1 incorrectly.

2. Step 2: Correct fraction calculation

   It should use floating division: (double)W / item.weight to get correct fraction value.

3. Final Answer:

   Using integer division in fraction calculation causes wrong value -> Option B

4. Quick Check:

   Integer division in fraction = error [OK]

Hint: Cast to double for fraction division to avoid integer truncation [OK]

Common Mistakes:

• Forgetting to cast to double in fraction
• Failing to sort items by value-to-weight ratio before iterating
• Declaring maxValue as int but adding fractions

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

hard

A. 180

B. 160

C. 190

D. 200

Solution

1. Step 1: Calculate value-to-weight ratios and sort

   Ratios:
   (40/2)=20, (100/20)=5, (50/10)=5, (60/12)=5
   Sorted order: (40,2), (100,20), (50,10), (60,12)

2. Step 2: Pick items to maximize value within capacity 30

   Take full (40,2): value=40, remaining=28
   Take full (100,20): value=140, remaining=8
   Next (50,10): only 8 weight left, fraction=8/10=0.8, value added=50*0.8=40
   Total value=40+100+40=180

3. Step 3: Check if next item can add value

   Last item (60,12) cannot be taken as capacity is full.

4. Final Answer:

   180 -> Option A

5. Quick Check:

   Sum values with fractions = 180 [OK]

Hint: Pick highest ratio items fully, then fractionally fill remaining [OK]

Common Mistakes:

• Ignoring highest ratio item first
• Taking items in wrong order
• Not calculating fraction correctly