The approximation hierarchy — how good can you get

The second layer of the complexity map: not all "approximable" problems are equally approximable.

1. 01
   The knapsack FPTAS — set an epsilon tolerance, scale every value down, run the DP on the smaller numbers, round back up. The result is within (1 − ε) of optimal in time polynomial in both the input and 1/ε. A quality knob you actually get to turn.

   fn knapsack_fptas(weights: &[u32], values: &[u32], capacity: u32, epsilon: f64) -> u64 {
       let v_max = *values.iter().max().unwrap_or(&1) as f64;
       let n = values.len() as f64;
       let k = (epsilon * v_max / n).max(1.0);
       let scaled: Vec<u32> = values.iter().map(|&v| (v as f64 / k) as u32).collect();
       let total: u32 = scaled.iter().sum();
       let mut dp = vec![u32::MAX; (total + 1) as usize];
       dp[0] = 0;
       for (i, &v) in scaled.iter().enumerate() {
           for s in (v..=total).rev() {
               if dp[(s - v) as usize] != u32::MAX {
                   dp[s as usize] = dp[s as usize].min(dp[(s - v) as usize] + weights[i]);
               }
           }
       }
       (0..=total)
           .filter(|&s| dp[s as usize] <= capacity)
           .map(|s| (s as f64 * k) as u64)
           .max()
           .unwrap_or(0)
   }

2. 02
   *values.iter().max().unwrap_or(&1) is a four-step chain that hides a lot of work in one line. Read it right-to-left. values.iter().max() walks the slice and returns the maximum, but as Option<&u32> — None if the slice is empty, Some(&max) otherwise. The Option exists because a max-of-an-empty-collection has no answer. .unwrap_or(&1) provides a default: if max() returned Some(&v) we keep &v, and if it returned None we substitute &1 so the rest of the chain has a value to work with. The fallback type has to match what max yields — &u32 — so it is &1, not just 1. Finally, the leading * dereferences the resulting &u32 back to a plain u32 so it can be cast to f64 for the subsequent floating-point arithmetic. Same chain in nine words: "the largest value, or 1 if there are none."

   // Read right-to-left to follow the type at each step:
   //
   //   *values.iter().max().unwrap_or(&1) as f64
   //   ────────────────────────────────── ────
   //             u32                       f64
   //
   //   values             : &[u32]
   //   values.iter()      : iterator of &u32
   //   .max()             : Option<&u32>       — Option, because slice may be empty
   //   .unwrap_or(&1)     : &u32                — Some(&v) kept; None substitutes &1
   //   *                  : u32                 — dereference the reference
   
   
   // Step by step on a concrete slice:
   let values: &[u32] = &[3, 7, 2, 9, 4];
   
   let m: Option<&u32> = values.iter().max();   // Some(&9)
   let m: &u32         = m.unwrap_or(&1);        // &9
   let m: u32          = *m;                      // 9
   
   
   // Why each piece is needed:
   //
   //   .iter()         iterating a borrowed slice yields REFERENCES (&u32),
   //                    not owned values — the slice doesn't own the data
   //                    and can't hand out copies; it hands out views.
   //
   //   .max()          returns Option<T> because the iterator might be
   //                    empty.  No max exists for an empty collection.
   //
   //   .unwrap_or(&1)  gives a fallback for the None case.  The type must
   //                    match what max yields, so &1 (a reference), not 1.
   //                    Defaulting to 1 here prevents downstream division
   //                    by zero when computing the scale factor k.
   //
   //   *               collapse &u32 → u32 so the value can be cast to f64.
   
   
   // Equivalent with a match expression — more verbose, same behaviour:
   let v_max: f64 = match values.iter().max() {
       Some(&v) => v as f64,
       None     => 1.0,
   };
   
   
   // Equivalent with .copied() (page 18) to strip the reference earlier:
   let v_max: f64 = values
       .iter()
       .copied()                            // iterator of u32 instead of &u32
       .max()                                // Option<u32>
       .unwrap_or(1) as f64;                 // u32, no deref needed
   
   
   // Family of "unwrap with a fallback" methods on Option<T>:
   //
   //   .unwrap_or(default)         supply a fallback value directly
   //   .unwrap_or_else(|| compute) compute the fallback lazily (only on None)
   //   .unwrap_or_default()         use T's Default::default() value (0, "", etc.)
   //
   // .unwrap_or_else is the right choice when the fallback is expensive to
   // build — the closure only runs in the None case.