Fractional Knapsack Problem in DSA Java - Execution Trace

Concept Flow - Fractional Knapsack Problem

Start with items sorted by value/weight ratio

↓

Initialize total weight = 0, total value = 0

↓

For each item in sorted list

↓

Can full item fit?

No→Take fraction of item to fill knapsack

|Yes↓

Add full item weight and value

↓

Update total weight and value

↓

Knapsack full?

No→Next item

|Yes↓

Done

The flow shows sorting items by value/weight ratio, then adding full or fractional parts until the knapsack is full.

Execution Sample

DSA Java

List<Item> items = Arrays.asList(new Item(60, 10), new Item(100, 20), new Item(120, 30));
int capacity = 50;
// Sort items by value/weight ratio descending
// Take items fully or fractionally until capacity is reached
// Calculate maximum total value

This Java code snippet sorts items by value per weight and fills the knapsack greedily to maximize total value.

Execution Table

Step	Operation	Item (Value, Weight)	Weight Taken	Value Added	Total Weight	Total Value	Knapsack State
1	Sort items by value/weight	[(60,10), (100,20), (120,30)]	-	-	0	0	[]
2	Take full item	(60,10)	10	60	10	60	[(60,10)]
3	Take full item	(100,20)	20	100	30	160	[(60,10), (100,20)]
4	Take fractional item	(120,30)	20	80	50	240	[(60,10), (100,20), (120,20)]
5	Knapsack full	-	-	-	50	240	Full capacity reached

💡 Knapsack capacity reached at total weight 50, no more items can be added.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
totalWeight	0	10	30	50	50
totalValue	0	60	160	240	240
knapsackState	[]	[(60,10)]	[(60,10), (100,20)]	[(60,10), (100,20), (120,20)]	[(60,10), (100,20), (120,20)]

Key Moments - 3 Insights

Why do we take only a fraction of the last item instead of the whole?

Because adding the whole last item would exceed the knapsack capacity, so we take only the fraction that fits (see Step 4 in execution_table).

Why do we sort items by value/weight ratio first?

Sorting ensures we pick items that give the most value per unit weight first, maximizing total value (see Step 1 in execution_table).

What happens if the knapsack capacity is exactly met?

The algorithm stops adding items once total weight equals capacity, as shown in Step 5 where knapsack is full.

Visual Quiz - 3 Questions

Look at the execution_table, what is the total value after Step 3?

A 160

B 100

C 60

D 240

💡 Hint

Check the 'Total Value' column at Step 3 in execution_table.

At which step does the knapsack reach full capacity?

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Look at the 'Knapsack State' and 'Total Weight' columns to see when capacity is reached.

If the capacity was 60 instead of 50, what would change in the execution_table?

A We would take the full last item instead of a fraction

B We would take fewer items

C The total value would decrease

D The sorting order would change

💡 Hint

Consider how capacity affects the fraction taken in Step 4.

Concept Snapshot

Fractional Knapsack Problem:
- Sort items by value/weight ratio descending
- Add full items while capacity allows
- Add fraction of next item if needed
- Maximize total value within capacity
- Greedy approach works for fractional items

Full Transcript

The Fractional Knapsack Problem involves selecting items with given values and weights to maximize total value without exceeding capacity. We first sort items by their value-to-weight ratio. Then, we add items fully if they fit or fractionally if only part fits. The process stops when the knapsack is full. This greedy method ensures maximum value. The execution table shows each step: sorting, adding full items, adding fractional item, and stopping when full. Variables track total weight, total value, and knapsack contents. Key moments clarify why sorting is needed, why fractional items are taken, and when the process stops. The quiz tests understanding of these steps and outcomes.

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