Fractional Knapsack Problem in DSA Java - Build from Scratch

Fractional Knapsack Problem

📖 Scenario: You are packing a bag for a hiking trip. You want to carry items that give you the most value, but your bag can only hold a limited weight. Some items can be broken into smaller parts, so you can take fractions of them.

🎯 Goal: Build a program that calculates the maximum total value you can carry in your bag by taking whole or fractional parts of items.

📋 What You'll Learn

Create an array of items with weight and value

Create a variable for the maximum weight the bag can hold

Calculate the maximum value using the fractional knapsack approach

Print the maximum value with two decimal places

💡 Why This Matters

🌍 Real World

This problem models packing and resource allocation where partial quantities can be taken, such as loading cargo or cutting materials.

💼 Career

Understanding greedy algorithms like fractional knapsack is important for optimization tasks in software engineering, logistics, and data science.

1

Create the items array

Create a class called Item with two public double fields: weight and value. Then create an array called items with these exact entries: new Item(10, 60), new Item(20, 100), new Item(30, 120).

DSA Java

// Define the Item class and create the items array
// Your code here

Hint

Define a class with two fields and create an array with three objects using the new keyword.

2

Set the maximum weight capacity

Inside the main method, create a double variable called maxWeight and set it to 50.

DSA Java

class Item {
    public double weight;
    public double value;

    public Item(double weight, double value) {
        this.weight = weight;
        this.value = value;
    }
}

public class FractionalKnapsack {
    public static void main(String[] args) {
        Item[] items = {
            new Item(10, 60),
            new Item(20, 100),
            new Item(30, 120)
        };
        // Create maxWeight variable here
        // Your code here
    }
}

Hint

Use a double variable to hold the maximum weight the bag can carry.

3

Calculate the maximum value using fractional knapsack

Add code inside the main method to calculate the maximum total value that fits into the bag with weight maxWeight. Sort the items array by value per weight in descending order. Then use a for loop with variable i to iterate over items. Use a variable totalValue initialized to 0. For each item, if the item's weight is less than or equal to the remaining capacity, add its full value to totalValue and reduce the remaining capacity. Otherwise, add the fractional value proportional to the remaining capacity and break the loop.

DSA Java

class Item {
    public double weight;
    public double value;

    public Item(double weight, double value) {
        this.weight = weight;
        this.value = value;
    }
}

public class FractionalKnapsack {
    public static void main(String[] args) {
        Item[] items = {
            new Item(10, 60),
            new Item(20, 100),
            new Item(30, 120)
        };
        double maxWeight = 50;
        // Calculate totalValue using fractional knapsack
        // Your code here
    }
}

Hint

Sort items by value/weight ratio. Use a loop to add full or fractional values until the bag is full.

4

Print the maximum total value

Add a print statement to display the totalValue rounded to two decimal places using System.out.printf.

DSA Java

import java.util.Arrays;
import java.util.Comparator;

class Item {
    public double weight;
    public double value;

    public Item(double weight, double value) {
        this.weight = weight;
        this.value = value;
    }
}

public class FractionalKnapsack {
    public static void main(String[] args) {
        Item[] items = {
            new Item(10, 60),
            new Item(20, 100),
            new Item(30, 120)
        };
        double maxWeight = 50;

        Arrays.sort(items, new Comparator() {
            public int compare(Item a, Item b) {
                double r1 = a.value / a.weight;
                double r2 = b.value / b.weight;
                if (r2 > r1) return 1;
                else if (r2 < r1) return -1;
                else return 0;
            }
        });

        double totalValue = 0;
        double remainingWeight = maxWeight;

        for (int i = 0; i < items.length; i++) {
            if (items[i].weight <= remainingWeight) {
                totalValue += items[i].value;
                remainingWeight -= items[i].weight;
            } else {
                totalValue += items[i].value * (remainingWeight / items[i].weight);
                break;
            }
        }
        // Print totalValue rounded to 2 decimals
        // Your code here
    }
}

Hint

Use System.out.printf("%.2f\n", totalValue); to print the value with two decimals.

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