Fractional Knapsack Problem in DSA Rust - 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 to fill knapsack

|Yes↓

Add full item value and weight

↓

Update total_weight and total_value

↓

Knapsack full?

No→Next item

|Yes↓

Done

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

Execution Sample

DSA Rust

items = [(weight=10, value=60), (weight=20, value=100), (weight=30, value=120)]
capacity = 50
Sort items by value/weight ratio
Take items fully or fractionally until capacity is reached

This code picks items or fractions to maximize value within capacity.

Execution Table

Step	Operation	Item (weight,value)	Can full item fit?	Fraction taken	Total weight	Total value	Knapsack state
1	Sort items by value/weight	(10,60), (20,100), (30,120)	N/A	N/A	0	0	Empty
2	Consider item 1	(10,60)	Yes (0+10 <= 50)	1.0	10	60	10/50 weight used, value=60
3	Consider item 2	(20,100)	Yes (10+20 <= 50)	1.0	30	160	30/50 weight used, value=160
4	Consider item 3	(30,120)	No (30+30 > 50)	0.6667	50	240	50/50 weight used, value=240
5	Knapsack full	N/A	N/A	N/A	50	240	Full - stop

💡 Knapsack reached full capacity at step 4 with fractional item taken.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
total_weight	0	10	30	50	50
total_value	0	60	160	240	240
fraction_taken_item3	0	0	0	0.6667	0.6667

Key Moments - 3 Insights

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

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

How do we decide the order of items to pick?

Items are sorted by their value-to-weight ratio before picking (step 1), ensuring we pick the most valuable per weight first.

What happens if the knapsack capacity is exactly met?

We stop picking items immediately (step 5), no more items or fractions are added.

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 become full?

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Look for when total_weight reaches capacity in execution_table.

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

A Fraction taken for item 3 would be 1.0 (full item taken)

B Fraction taken for item 2 would be less than 1.0

C Total value after step 4 would be less than 240

D Knapsack would be full at step 3

💡 Hint

Consider if full item 3 fits with increased capacity in variable_tracker.

Concept Snapshot

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

Full Transcript

The Fractional Knapsack Problem involves selecting items with given weights and values 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 partially if only a fraction fits. We track total weight and value after each addition. The process stops when the knapsack is full. This greedy method ensures maximum value for fractional items.

Practice

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

easy

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

B. Minimize total weight by selecting whole items only

C. Maximize number of items regardless of weight

D. Select items randomly without considering value or weight

Solution

1. Step 1: Understand problem objective

   The fractional knapsack problem aims to maximize the total value of items placed in a knapsack without exceeding its weight capacity.

2. Step 2: Recognize fractional selection

   Unlike the 0/1 knapsack, it allows taking fractions of items to fill the knapsack optimally.

3. Final Answer:

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

4. Quick Check:

   Goal = maximize value with fractions [OK]

Hint: Remember: fractional means partial items allowed [OK]

Common Mistakes:

• Thinking only whole items can be taken
• Confusing with minimizing weight
• Ignoring value-to-weight ratio

2. Which Rust code snippet correctly defines a struct to represent an item with weight and value for the fractional knapsack?

easy

A. struct Item { weight: usize, value: bool }

B. struct Item { weight: f64, value: f64 }

C. struct Item { weight: String, value: String }

D. struct Item(weight: i32, value: i32);

Solution

1. Step 1: Identify correct struct syntax

   Rust structs use curly braces with field names and types, e.g., struct Item { weight: f64, value: f64 }.

2. Step 2: Check field types for fractional knapsack

   Weights and values can be fractional, so f64 (floating-point) is appropriate.

3. Final Answer:

   struct Item { weight: f64, value: f64 } -> Option B

4. Quick Check:

   Correct struct syntax with f64 fields [OK]

Hint: Use f64 for fractional weights and values [OK]

Common Mistakes:

• Using tuple struct syntax incorrectly
• Using integer or wrong types for fractional values
• Using incompatible types like String or bool

3. What is the output of this Rust code snippet that calculates maximum value for fractional knapsack?

struct Item { weight: f64, value: f64 }

fn fractional_knapsack(items: &mut Vec<Item>, capacity: f64) -> f64 {
    items.sort_by(|a, b| (b.value / b.weight).partial_cmp(&(a.value / a.weight)).unwrap());
    let mut total_value = 0.0;
    let mut remaining = capacity;
    for item in items.iter() {
        if item.weight <= remaining {
            total_value += item.value;
            remaining -= item.weight;
        } else {
            total_value += item.value * (remaining / item.weight);
            break;
        }
    }
    total_value
}

fn main() {
    let mut items = vec![
        Item { weight: 10.0, value: 60.0 },
        Item { weight: 20.0, value: 100.0 },
        Item { weight: 30.0, value: 120.0 },
    ];
    let capacity = 50.0;
    let max_value = fractional_knapsack(&mut items, capacity);
    println!("{:.2}", max_value);
}

medium

A. 180.00

B. 220.00

C. 200.00

D. 240.00

Solution

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

   Ratios: 60/10=6, 100/20=5, 120/30=4. Sorted order: Item1, Item2, Item3.

2. Step 2: Add items until capacity 50

   Add Item1 fully (weight 10, value 60), remaining 40.
   Add Item2 fully (weight 20, value 100), remaining 20.
   Add fraction of Item3: fraction = 20/30 = 2/3, value = 120 * 2/3 = 80.
   Total value = 60 + 100 + 80 = 240.

3. Final Answer:

   240.00 -> Option D

4. Quick Check:

   Sum values with fractions = 240.00 [OK]

Hint: Sort by value/weight ratio, fill capacity greedily [OK]

Common Mistakes:

• Not sorting items by ratio
• Taking whole items only
• Incorrect fraction calculation

4. Identify the bug in this Rust function for fractional knapsack:

fn fractional_knapsack(items: &mut Vec<Item>, capacity: f64) -> f64 {
    items.sort_by(|a, b| (a.value / a.weight).partial_cmp(&(b.value / b.weight)).unwrap());
    let mut total_value = 0.0;
    let mut remaining = capacity;
    for item in items.iter() {
        if item.weight <= remaining {
            total_value += item.value;
            remaining -= item.weight;
        } else {
            total_value += item.value * (remaining / item.weight);
            break;
        }
    }
    total_value
}

medium

A. Sorting order is ascending, should be descending by value/weight

B. Using iter() instead of into_iter() causes ownership error

C. Incorrect calculation of fractional value inside else block

D. Missing return statement at the end of function

Solution

1. Step 1: Check sorting comparator

   The code sorts by (a.value / a.weight).partial_cmp(&(b.value / b.weight)), which sorts ascending by ratio.

2. Step 2: Correct sorting order for greedy approach

   Fractional knapsack requires descending order by value/weight ratio to pick highest value items first.

3. Final Answer:

   Sorting order is ascending, should be descending by value/weight -> Option A

4. Quick Check:

   Sort descending by ratio for max value [OK]

Hint: Sort descending by value/weight ratio, not ascending [OK]

Common Mistakes:

• Sorting ascending instead of descending
• Confusing iter() and into_iter() ownership
• Miscomputing fractional value

5. Given items with weights and values:
[(5, 30), (10, 40), (15, 45)] and knapsack capacity 20, what is the maximum value using fractional knapsack?

hard

A. 70

B. 80

C. 85

D. 75

Solution

1. Step 1: Calculate value/weight ratios and sort descending

   Ratios: 30/5=6, 40/10=4, 45/15=3.
   Sorted order: (5,30), (10,40), (15,45).

2. Step 2: Fill knapsack capacity 20 greedily

   Take full (5,30), remaining 15, total value 30.
   Take full (10,40), remaining 5, total value 70.
   Take fraction of (15,45): fraction = 5/15 = 1/3, value = 45 * 1/3 = 15.
   Total value = 70 + 15 = 85.

3. Step 3: Verify options

   85 is 85, matching calculation.

4. Final Answer:

   85 -> Option C

5. Quick Check:

   Greedy fill with fractions = 85 [OK]

Hint: Sort by ratio, fill capacity fully, then fractionally [OK]

Common Mistakes:

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