Fractional Knapsack Problem in DSA Rust - Build from Scratch

Fractional Knapsack Problem

📖 Scenario: You are packing a bag for a hiking trip. You have several items, each with a weight and a value. Your bag can only carry a limited weight. You want to maximize the total value of items in your bag. You can take fractions of items if needed.

🎯 Goal: Build a Rust program that calculates the maximum value you can carry in your bag using the fractional knapsack approach.

📋 What You'll Learn

Create a vector of tuples called items where each tuple contains weight and value as f64.

Create a variable called capacity of type f64 representing the maximum weight the bag can carry.

Sort the items vector by value-to-weight ratio in descending order.

Calculate the maximum value that fits in the bag using fractional parts of items if needed.

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 budgeting.

💼 Career

Understanding greedy algorithms like fractional knapsack is useful for optimization problems in software engineering, logistics, and finance.

1

Create the list of items

Create a vector called items with these exact tuples of (weight, value) as f64: (10.0, 60.0), (20.0, 100.0), (30.0, 120.0).

DSA Rust

# Create the vector items with tuples (weight, value) as f64
# Your code here

Hint

Use let mut items: Vec<(f64, f64)> = vec![(10.0, 60.0), (20.0, 100.0), (30.0, 120.0)];

2

Set the bag capacity

Create a variable called capacity of type f64 and set it to 50.0.

DSA Rust

fn main() {
    let mut items: Vec = vec![(10.0, 60.0), (20.0, 100.0), (30.0, 120.0)];
    // Create capacity variable here
    // Your code here
}

Hint

Use let capacity: f64 = 50.0; to set the bag capacity.

3

Sort items by value-to-weight ratio and calculate max value

Sort the items vector by value-to-weight ratio in descending order using sort_by. Then create a variable total_value of type f64 set to 0.0. Use a for loop with variables weight and value to iterate over items. Inside the loop, if capacity is zero, break. Otherwise, take the minimum of weight and capacity as amount. Add amount * (value / weight) to total_value. Subtract amount from capacity.

DSA Rust

fn main() {
    let mut items: Vec = vec![(10.0, 60.0), (20.0, 100.0), (30.0, 120.0)];
    let mut capacity: f64 = 50.0;
    // Sort items by value-to-weight ratio descending
    // Calculate total_value using fractional knapsack logic
    // Your code here
}

Hint

Sort with items.sort_by(|a, b| ((b.1 / b.0).partial_cmp(&(a.1 / a.0))).unwrap()); and use a loop to add fractional values.

4

Print the maximum value

Print the total_value rounded to two decimal places using println!("{:.2}", total_value);.

DSA Rust

fn main() {
    let mut items: Vec = vec![(10.0, 60.0), (20.0, 100.0), (30.0, 120.0)];
    let mut capacity: f64 = 50.0;
    items.sort_by(|a, b| ((b.1 / b.0).partial_cmp(&(a.1 / a.0))).unwrap());
    let mut total_value: f64 = 0.0;
    for (weight, value) in items {
        if capacity == 0.0 {
            break;
        }
        let amount = if weight < capacity { weight } else { capacity };
        total_value += amount * (value / weight);
        capacity -= amount;
    }
    // Print total_value rounded to 2 decimals
    // Your code here
}

Hint

Use println!("{:.2}", total_value); to print the result.

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