0/1 Knapsack (Small)

Fill a small 0/1 knapsack table where each row decides whether one more item is available.

Algorithm

Steps

Create a table with one extra row for using zero items.
Process the four items in fixed order.
For each capacity, inherit when the item is too heavy.
Otherwise compare skip and take from the previous row.
Print the best value and the full deterministic table.

Complexity

Time: O(item_count * capacity)
Space: O(item_count * capacity)

state transition `dp[i][w]` compares skipping item `i` with taking it and reading the remaining capacity from the previous row.

Rust DSA Implementation

basic.rs

fn row_string(row: &[i32]) -> String {
    format!("[{}]", row.iter().map(|v| v.to_string()).collect::<Vec<_>>().join(", "))
}
fn table_string(table: &[Vec<i32>]) -> String {
    format!("[{}]", table.iter().map(|r| row_string(r)).collect::<Vec<_>>().join(", "))
}
fn main() {
    let weights = [2usize, 3, 4, 5];
    let values = [3, 4, 5, 6];
    let capacity = 5usize;
    let mut dp = vec![vec![0; capacity + 1]; weights.len() + 1];
    for item in 1..=weights.len() {
        let weight = weights[item - 1];
        let value = values[item - 1];
        for cap in 0..=capacity {
            if weight > cap {
                dp[item][cap] = dp[item - 1][cap];
            } else {
                let skip = dp[item - 1][cap];
                let take = value + dp[item - 1][cap - weight];
                dp[item][cap] = skip.max(take);
            }
        }
    }
    println!("{}", dp[weights.len()][capacity]);
    println!("{}", table_string(&dp));
}

Output

7
[[0, 0, 0, 0, 0, 0], [0, 0, 3, 3, 3, 3], [0, 0, 3, 4, 4, 7], [0, 0, 3, 4, 5, 7], [0, 0, 3, 4, 5, 7]]

Implementation notes

Rust stores weights as [usize; 4], values as inferred [i32; 4], and capacity is 5usize, matching the table indexes used in the loops.
let mut dp = vec![vec![0; capacity + 1]; weights.len() + 1] builds a Vec<Vec<i32>> with five independent rows and six columns, all initialized to zero.
The outer loop for item in 1..=weights.len() maps row item to weights[item - 1] and values[item - 1]; those scalar values are copied out of the fixed arrays.
The inner loop scans cap from 0..=capacity. If weight > cap, the cell copies dp[item - 1][cap] from the previous row.
Otherwise the update reads only the previous row: skip = dp[item - 1][cap], take = value + dp[item - 1][cap - weight], then stores skip.max(take).
The trace records row states after each item: [0, 0, 3, 3, 3, 3], [0, 0, 3, 4, 4, 7], [0, 0, 3, 4, 5, 7], and [0, 0, 3, 4, 5, 7].
println!("{}", dp[weights.len()][capacity]) prints 7; table_string(&dp) borrows the table rows and formats the full table for the second println!.