Knapsack — which items fit in the budget

Knapsack is NP-complete but practically cheap when the numbers are small. One of the friendliest hard problems.

1. 01
   The classic DP runs in O(items · budget) — fast whenever the budget is a small integer. For an engineering portfolio of a hundred features and a budget in story points, this is microseconds. Reach for good_lp when the budget is huge.

   fn knapsack(weights: &[u32], values: &[u32], capacity: u32) -> u32 {
       let n = weights.len();
       let cap = capacity as usize;
       let mut dp = vec![0u32; cap + 1];
       for i in 0..n {
           let w = weights[i] as usize;
           let v = values[i];
           if w > cap { continue; }
           for c in (w..=cap).rev() {
               dp[c] = dp[c].max(dp[c - w] + v);
           }
       }
       dp[cap]
   }

2. 02
   &[u32] is a slice of u32 values, taken by reference. Two layers: [u32] is the slice type (an unsized, runtime-length sequence of u32), and the outer & borrows it. At runtime the compiler stores this as a fat pointer — a (data pointer, length) pair — so the function knows where the data lives and how many entries are valid. &[T] is the maximally permissive read-only parameter type for any contiguous sequence: a Vec<u32> coerces via &vec, an array [u32; N] coerces via &arr, and a literal &[1, 2, 3] is one directly. Same rule as page 14 applied to numeric sequences — prefer &[T] over Vec<T> for read-only parameters. It borrows instead of demanding ownership, and it accepts every shape callers might already have.

   // &[u32] decoded:
   //
   //   & [ u32 ]
   //   ─ ─────
   //   │  │
   //   │  └── [u32] — an unsized sequence of u32 values
   //   └──── & — a shared borrow of that sequence
   
   fn knapsack(weights: &[u32], values: &[u32], capacity: u32) -> u32 { /* ... */ }
   
   
   // Every call below works because the source coerces to &[u32]:
   knapsack(&[2, 3, 4], &[3, 4, 5], 8);                 // array literal
   
   let v: Vec<u32> = vec![2, 3, 4];
   let w: Vec<u32> = vec![3, 4, 5];
   knapsack(&v, &w, 8);                                  // Vec<u32> → &[u32]
   knapsack(v.as_slice(), w.as_slice(), 8);              // explicit .as_slice()
   knapsack(&v[1..], &w[1..], 8);                        // sub-slice of a slice
   
   let arr: [u32; 3] = [2, 3, 4];
   knapsack(&arr, &[3, 4, 5], 8);                        // fixed-size array → &[u32]
   
   
   // Fat pointer — what's actually stored at runtime:
   //
   //   &[u32]
   //   ┌──────────────┬────────┐
   //   │ data pointer │ length │     16 bytes on a 64-bit target
   //   └──────────────┴────────┘
   //
   // The pointer says where the bytes live; the length tells the compiler
   // how many u32 values are valid.  Indexing is bounds-checked against
   // that length — no buffer overruns.
   
   
   // Why prefer &[T] over Vec<T> for read-only parameters:
   //   • borrows instead of demanding ownership
   //   • accepts Vec, arrays, sub-slices, literals — every shape
   //   • the signature declares "I will only read, not grow or shrink"
   //
   // Reach for Vec<T> as a parameter only when the function genuinely needs
   // to take ownership (e.g., to store or move it elsewhere).  Reach for
   // &mut [T] when it needs to mutate elements in place but not change length.
   
   
   // The slice family across this book:
   //   &[u32]      weights / values list — read-only sequence of numbers
   //   &str        a string slice (page 4) — the same idea applied to bytes
   //   &[&str]     a list of string references (page 17)
   //   &mut [T]    a writable slice — used for in-place sorting and shuffling