Code shared from the Rust Playground

knapsack.rs

/// Solves the 0/1 Knapsack problem using Dynamic Programming.
///
/// # Arguments
/// * `max_weight` - The maximum weight capacity of the knapsack.
/// * `weights` - A slice containing the weights of the available items.
/// * `values` - A slice containing the values of the available items.
///
/// # Returns
/// The maximum value that can be accommodated within the given capacity.
pub fn knapsack(max_weight: usize, weights: &[usize], values: &[usize]) -> usize {
    let n = weights.len();
    
    // Create a 2D dynamic programming table initialized to 0.
    // dp[i][w] will store the maximum value that can be attained with 
    // a knapsack of capacity 'w' using a subset of the first 'i' items.
    let mut dp = vec![vec![0; max_weight + 1]; n + 1];

    // Build the dp table in a bottom-up manner
    for i in 0..=n {
        for w in 0..=max_weight {
            if i == 0 || w == 0 {
                // Base case: 0 items or 0 capacity means 0 value
                dp[i][w] = 0;
            } else if weights[i - 1] <= w {
                // If the current item's weight is less than or equal to the current capacity,
                // we have two choices: include the item or exclude it.
                // We take the maximum of these two possibilities.
                let include_item = values[i - 1] + dp[i - 1][w - weights[i - 1]];
                let exclude_item = dp[i - 1][w];
                
                dp[i][w] = include_item.max(exclude_item);
            } else {
                // If the current item's weight exceeds the current capacity 'w',
                // it cannot be included. The maximum value is the same as excluding it.
                dp[i][w] = dp[i - 1][w];
            }
        }
    }

    // The bottom-right cell of the table contains the final answer
    dp[n][max_weight]
}

fn main() {
    // Example dataset
    let values = vec![60, 100, 120];
    let weights = vec![10, 20, 30];
    let max_weight = 50;

    println!("--- 0/1 Knapsack Problem ---");
    println!("Items available:");
    for i in 0..values.len() {
        println!("  Item {}: Value = {}, Weight = {}", i + 1, values[i], weights[i]);
    }
    
    println!("\nKnapsack Capacity: {}", max_weight);

    // Execute the algorithm
    let max_value = knapsack(max_weight, &weights, &values);
    
    println!("Maximum value achievable: {}", max_value);
}

https://play.rust-lang.org/?version=stable&mode=debug&edition=2024&gist=8d0d2a5398618a79ebe1e80a68d09451