Why Fractional Knapsack Problem in DSA Java?

The Big Idea

What if you could carry the most valuable parts of your items instead of whole things and never waste space again?

The Scenario

Imagine you have a backpack with limited weight capacity, and you want to fill it with items to get the most value. You try to pick items one by one without a plan, sometimes taking whole items that are too heavy or missing out on valuable parts.

The Problem

Picking items manually without a strategy is slow and often leads to poor choices. You might carry heavy items with low value and miss out on smaller parts of high-value items. This wastes space and reduces your total gain.

The Solution

The Fractional Knapsack Problem helps by allowing you to take fractions of items based on their value-to-weight ratio. This way, you fill your backpack optimally, maximizing total value without wasting space.

Before vs After

✗ Before

int totalValue = 0;
for (Item item : items) {
  if (item.weight <= capacity) {
    capacity -= item.weight;
    totalValue += item.value;
  }
}

✓ After

Arrays.sort(items, (a, b) -> Double.compare(b.valuePerWeight, a.valuePerWeight));
double totalValue = 0;
for (Item item : items) {
  if (capacity == 0) break;
  double weightTaken = Math.min(item.weight, capacity);
  totalValue += weightTaken * item.valuePerWeight;
  capacity -= weightTaken;
}

What It Enables

This concept enables you to maximize the total value you carry by smartly choosing whole or partial items based on their worth per weight.

Real Life Example

Think of packing a suitcase for a trip where you can only carry a certain weight. Instead of packing whole heavy items, you take only the parts you need most, like a portion of food or a small bottle of shampoo, to get the most benefit.

Key Takeaways

Manual picking wastes space and value.

Fractional Knapsack uses value-to-weight ratio for optimal packing.

Allows taking parts of items to maximize total value.

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