Fractional Knapsack Problem in DSA Rust

Mental Model

We want to fill a bag with items to get the most value, and we can take parts of items if needed.

Analogy: Imagine filling a jar with different types of honey. Each honey has a price per spoon. You want to fill the jar to get the most expensive honey first, even if you only take a spoonful.

Bag capacity: 50
Items:
[Item1: weight=10, value=60]
[Item2: weight=20, value=100]
[Item3: weight=30, value=120]

Sorted by value/weight ratio:
[Item1: 6.0] -> [Item2: 5.0] -> [Item3: 4.0]

Bag filling -> 0/50 full

Dry Run Walkthrough

Input: items: [(weight=10, value=60), (weight=20, value=100), (weight=30, value=120)], capacity=50

Goal: Maximize total value in the bag by taking whole or fractional parts of items

Step 1: Sort items by value/weight ratio descending

[Item1: w=10, v=60, ratio=6.0] -> [Item2: w=20, v=100, ratio=5.0] -> [Item3: w=30, v=120, ratio=4.0]

Why: We want to pick items with the highest value per weight first to maximize total value

Step 2: Take whole Item1 (weight 10) into bag

Bag: 10/50 full, Value: 60

Why: Item1 fits fully, so take it all to add maximum value

Step 3: Take whole Item2 (weight 20) into bag

Bag: 30/50 full, Value: 160

Why: Item2 fits fully, so take it all to add more value

Step 4: Take fraction of Item3 to fill remaining capacity (20/30 fraction)

Bag: 50/50 full, Value: 160 + (120 * 20/30) = 240

Why: Only part of Item3 fits, so take fraction to fill bag and maximize value

Result:

Bag full: 50/50
Total value: 240

Annotated Code

DSA Rust

use std::cmp::Ordering;

#[derive(Debug)]
struct Item {
    weight: f64,
    value: f64,
}

impl Item {
    fn value_per_weight(&self) -> f64 {
        self.value / self.weight
    }
}

fn fractional_knapsack(items: &mut [Item], capacity: f64) -> f64 {
    // Sort items by value per weight ratio descending
    items.sort_by(|a, b| b.value_per_weight().partial_cmp(&a.value_per_weight()).unwrap_or(Ordering::Equal));

    let mut total_value = 0.0;
    let mut remaining_capacity = capacity;

    for item in items.iter() {
        if remaining_capacity == 0.0 {
            break; // bag is full
        }

        if item.weight <= remaining_capacity {
            // Take whole item
            total_value += item.value;
            remaining_capacity -= item.weight;
        } else {
            // Take fraction of item
            let fraction = remaining_capacity / item.weight;
            total_value += item.value * fraction;
            remaining_capacity = 0.0; // bag is full
        }
    }

    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!("Maximum value in the knapsack: {:.2}", max_value);
}

items.sort_by(|a, b| b.value_per_weight().partial_cmp(&a.value_per_weight()).unwrap_or(Ordering::Equal));

Sort items by descending value per weight ratio to prioritize high value density

for item in items.iter() {

Iterate over sorted items to fill the knapsack

if item.weight <= remaining_capacity {

Check if whole item fits in remaining capacity

total_value += item.value;

Add full item value to total

remaining_capacity -= item.weight;

Reduce remaining capacity by item weight

let fraction = remaining_capacity / item.weight;

Calculate fraction of item to take if it doesn't fully fit

total_value += item.value * fraction;

Add fractional value to total

remaining_capacity = 0.0;

Knapsack is full after taking fraction

Output

Maximum value in the knapsack: 240.00

Complexity Analysis

Time: O(n log n) because we sort n items by value per weight ratio

Space: O(1) additional space since sorting is in-place and only a few variables are used

vs Alternative: Compared to trying all combinations (exponential), this greedy approach is efficient and optimal for fractional knapsack

Edge Cases

Empty items list

Returns 0.0 value since no items to take

DSA Rust

for item in items.iter() {

Capacity zero

Returns 0.0 value since no capacity to take any item

DSA Rust

if remaining_capacity == 0.0 { break; }

Item with zero weight

Avoid division by zero by sorting safely; code assumes positive weights

DSA Rust

items.sort_by(|a, b| b.value_per_weight().partial_cmp(&a.value_per_weight()).unwrap_or(Ordering::Equal));

When to Use This Pattern

When you need to maximize value with partial items allowed and a weight limit, use the fractional knapsack greedy pattern by sorting items by value density.

Common Mistakes

Mistake: Trying to take items in input order without sorting by value/weight ratio
Fix: Sort items descending by value per weight ratio before selecting

Mistake: Not handling fractional part when item doesn't fully fit
Fix: Calculate fraction of item to take based on remaining capacity

Summary

It finds the maximum total value by taking whole or fractional parts of items within capacity.

Use it when you can split items and want to maximize value under a weight limit.

The key insight is to pick items by highest value per weight ratio first, taking fractions if needed.

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