Fractional Knapsack Problem in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Fractional Knapsack Calculation

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

DSA Java

import java.util.*;
class Item {
    int value, weight;
    Item(int v, int w) { value = v; weight = w; }
}
public class FractionalKnapsack {
    public static double getMaxValue(int W, Item[] items) {
        Arrays.sort(items, (a, b) -> Double.compare((double)b.value / b.weight, (double)a.value / a.weight));
        double totalValue = 0.0;
        int capacity = W;
        for (Item item : items) {
            if (capacity == 0) break;
            if (item.weight <= capacity) {
                capacity -= item.weight;
                totalValue += item.value;
            } else {
                totalValue += item.value * ((double)capacity / item.weight);
                capacity = 0;
            }
        }
        return totalValue;
    }
    public static void main(String[] args) {
        Item[] items = {new Item(60, 10), new Item(100, 20), new Item(120, 30)};
        int W = 50;
        System.out.printf("%.2f", getMaxValue(W, items));
    }
}

A 220.00

B 240.00

C 180.00

D 200.00

💡 Hint

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

The items sorted by value/weight ratio are: (60/10=6), (100/20=5), (120/30=4). The knapsack capacity is 50.

Take all of item 1 (weight 10, value 60), capacity left 40.

Take all of item 2 (weight 20, value 100), capacity left 20.

Take 20/30 fraction of item 3: value = 120 * (20/30) = 80.

Total value = 60 + 100 + 80 = 240.

🧠 Conceptual

intermediate

Key Property of Fractional Knapsack Problem

Which property allows the fractional knapsack problem to be solved optimally using a greedy approach?

A Items can be broken into smaller parts and taken fractionally

B All items have the same weight

C The knapsack capacity is unlimited

D Items must be taken whole or not at all

💡 Hint

Think about what makes fractional knapsack different from 0/1 knapsack.

The fractional knapsack problem allows taking fractions of items, which enables a greedy strategy by selecting items with the highest value-to-weight ratio first.

🔧 Debug

advanced

Identify the Error in Fractional Knapsack Code

What error will occur when running this Java code snippet for fractional knapsack?

DSA Java

import java.util.*;
class Item {
    int value, weight;
    Item(int v, int w) { value = v; weight = w; }
}
public class FractionalKnapsack {
    public static double getMaxValue(int W, Item[] items) {
        Arrays.sort(items, (a, b) -> (b.value / b.weight) - (a.value / a.weight));
        double totalValue = 0.0;
        int capacity = W;
        for (Item item : items) {
            if (capacity == 0) break;
            if (item.weight <= capacity) {
                capacity -= item.weight;
                totalValue += item.value;
            } else {
                totalValue += item.value * ((double)capacity / item.weight);
                capacity = 0;
            }
        }
        return totalValue;
    }
}

A Compilation error due to invalid lambda expression

B Runtime error: division by zero

C Incorrect sorting due to integer division causing wrong output

D No error, code runs correctly

💡 Hint

Check how integer division behaves in Java inside the comparator.

The comparator uses integer division (b.value / b.weight) which truncates decimals, causing incorrect sorting order. This leads to wrong greedy selection and incorrect final value.

🚀 Application

advanced

Maximum Value with Given Items and Capacity

Given items with values and weights: (value=40, weight=2), (value=100, weight=20), (value=50, weight=10), and knapsack capacity 30, what is the maximum value achievable using fractional knapsack?

A 140.00

B 150.00

C 160.00

D 180.00

💡 Hint

Calculate value/weight ratio and pick items greedily until capacity is full.

Value/weight ratios: 40/2=20, 100/20=5, 50/10=5.

Take all of item 1 (weight 2, value 40), capacity left 28.

Next items have same ratio 5, take all of item 3 (weight 10, value 50), capacity left 18.

Take 18/20 fraction of item 2: value = 100 * (18/20) = 90.

Total value = 40 + 50 + 90 = 180.

🧠 Conceptual

expert

Why Fractional Knapsack is Not Solvable by Dynamic Programming Like 0/1 Knapsack

Why is the fractional knapsack problem not typically solved using dynamic programming like the 0/1 knapsack problem?

A Because fractional knapsack allows partial items, making the problem continuous and solvable greedily

B Because fractional knapsack requires sorting items by weight only

C Because dynamic programming cannot handle any knapsack problem

D Because fractional knapsack has fewer items than 0/1 knapsack

💡 Hint

Consider the nature of the problem: discrete vs continuous.

Fractional knapsack allows taking fractions of items, making it a continuous optimization problem solvable optimally by a greedy approach. Dynamic programming is used for discrete problems like 0/1 knapsack where items cannot be split.

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