Fractional Knapsack Problem in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Fractional Knapsack with Given Items

What is the maximum value obtained by the fractional knapsack algorithm for the given items and capacity?

DSA Rust

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

fn fractional_knapsack(items: &mut [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 = capacity;
    for item in items {
        if item.weight <= remaining_capacity {
            total_value += item.value;
            remaining_capacity -= item.weight;
        } else {
            total_value += item.value * (remaining_capacity / item.weight);
            break;
        }
    }
    total_value
}

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

A 240.00

B 200.00

C 180.00

D 220.00

💡 Hint

Sort items by value-to-weight ratio and take as much as possible from the highest ratio items first.

The fractional knapsack algorithm sorts items by their value-to-weight ratio in descending order. It then takes whole items until the capacity is reached, and finally takes a fraction of the next item if needed.

For the given items, the ratios are:

• Item 1: 60/10 = 6
• Item 2: 100/20 = 5
• Item 3: 120/30 = 4

We take all of item 1 (weight 10, value 60), all of item 2 (weight 20, value 100), and 20 weight units of item 3 (since capacity left is 20), which gives 120 * (20/30) = 80 value.

Total value = 60 + 100 + 80 = 240.

🧠 Conceptual

intermediate

Key Property of Fractional Knapsack Problem

Which property allows the fractional knapsack problem to be solved optimally using a greedy approach?

A Items can be broken into smaller parts and taken fractionally

B All items have the same weight

C Items must be taken whole or not at all

D The knapsack capacity is unlimited

💡 Hint

Think about what makes greedy choice optimal here.

The fractional knapsack problem allows taking fractions of items, which means we can always take the most valuable part first. This property makes the greedy approach optimal.

In contrast, the 0/1 knapsack problem requires whole items, which is not solvable optimally by a simple greedy method.

🔧 Debug

advanced

Identify the Bug in Fractional Knapsack Implementation

What error will this Rust code produce when running the fractional knapsack function?

DSA Rust

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

fn fractional_knapsack(items: &mut [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 = capacity;
    for item in items {
        if item.weight <= remaining_capacity {
            total_value += item.value;
            remaining_capacity -= item.weight;
        } else {
            total_value += item.value * (remaining_capacity / item.weight);
            break;
        }
    }
    total_value
}

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

A Compilation error due to missing semicolon after sort_by

B No error, outputs correct maximum value

C Runtime panic due to division by zero

D The items are sorted in ascending order of value-to-weight ratio, causing incorrect output

💡 Hint

Check the sorting order of items by value-to-weight ratio.

The code sorts items by ascending order of value-to-weight ratio because it compares a.value/a.weight to b.value/b.weight directly without reversing the order.

This causes the algorithm to pick the least valuable items first, resulting in a suboptimal total value.

📝 Syntax

advanced

Syntax Error in Fractional Knapsack Code

Which option contains a syntax error that prevents the Rust code from compiling?

DSA Rust

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

fn fractional_knapsack(items: &mut [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 = capacity;
    for item in items {
        if item.weight <= remaining_capacity {
            total_value += item.value;
            remaining_capacity -= item.weight;
        } else {
            total_value += item.value * (remaining_capacity / item.weight);
            break;
        }
    }
    total_value
}

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

A Incorrect function return type, should be usize

B Missing closing brace for struct Item

C Missing semicolon after 'let mut total_value = 0.0' line

D Missing parentheses in println! macro

💡 Hint

Look carefully at the variable declarations inside the function.

The line 'let mut total_value = 0.0' is missing a semicolon at the end, causing a syntax error.

All other parts have correct syntax.

🚀 Application

expert

Maximum Value with Fractional Knapsack for Custom Input

Given the following items and knapsack capacity, what is the maximum value the fractional knapsack algorithm will return?

DSA Rust

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

fn fractional_knapsack(items: &mut [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 = capacity;
    for item in items {
        if item.weight <= remaining_capacity {
            total_value += item.value;
            remaining_capacity -= item.weight;
        } else {
            total_value += item.value * (remaining_capacity / item.weight);
            break;
        }
    }
    total_value
}

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

A 1300.00

B 1000.00

C 1100.00

D 1400.00

💡 Hint

Calculate value-to-weight ratios and take items in descending order until capacity is full.

Calculate value-to-weight ratios:

• Item 1: 500/50 = 10
• Item 2: 400/40 = 10
• Item 3: 300/30 = 10
• Item 4: 200/20 = 10

All ratios are equal at 10, so the maximum value is 10 * 100 = 1000.00 regardless of selection order.

The code sorts by descending ratio (stable for equals), takes Item 1 (50w, 500v), Item 2 (40w, 400v), then 10/30 of Item 3 (100v), totaling 1000.00.

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