Bin packing — fit the items into the fewest containers

Bin packing is the workhorse hard problem. When it shows up, the approximation is usually good enough.

1. 01
   First-Fit-Decreasing — sort items by descending size, place each in the first bin that fits. At most 11/9 of optimal, usually within a few percent on real workloads. Twenty lines of Rust replaces a quarter of bespoke search code.

   fn first_fit_decreasing(sizes: &[u32], capacity: u32) -> Vec<Vec<u32>> {
       let mut items = sizes.to_vec();
       items.sort_unstable_by(|a, b| b.cmp(a));
       let mut bins: Vec<Vec<u32>> = Vec::new();
       for size in items {
           let used: Vec<u32> = bins.iter().map(|b| b.iter().sum()).collect();
           match used.iter().position(|&u| u + size <= capacity) {
               Some(i) => bins[i].push(size),
               None => bins.push(vec![size]),
           }
       }
       bins
   }

2. 02
   Vec::new() and vec![] both produce an empty Vec — for the empty case they are equivalent (the vec! macro literally expands to Vec::new() when there are no elements). Neither allocates heap memory until the first push. The choice between them is stylistic. Convention: reach for Vec::new() when you are declaring an empty vec that will be filled later (the constructor name is visible — "I am starting empty"); reach for the vec! macro when you have initial contents (vec![1, 2, 3]) or the repeat form (vec![0; n]). Two practical differences exist. Vec::new() is a const fn, so it works in const contexts where the macro does not. And with an explicit type annotation on the binding, = Vec::new() reads slightly more clearly than = vec![] — the constructor name reinforces what the line is doing. A third constructor worth knowing is Vec::with_capacity(n) — empty (.len() == 0) but pre-allocated room for n elements, useful when you know roughly how many items will be pushed and want to skip the doubling reallocations a growing vec performs.

   // Three ways to create a Vec, each useful in different cases.
   
   // 1. Empty, no allocation yet.  Either form works; vec![] is the macro
   //    and Vec::new() is the constructor — equivalent for the empty case.
   let v: Vec<i32> = Vec::new();              // constructor form
   let v: Vec<i32> = vec![];                   // macro form
   
   // 2. With initial contents — the macro is the obvious choice.
   let v: Vec<i32> = vec![1, 2, 3];            // literal form
   let v: Vec<i32> = vec![0; 100];             // repeat form: 100 zeros
   
   // 3. Empty but with pre-allocated capacity — neither of the above.
   let v: Vec<i32> = Vec::with_capacity(100);  // empty (len == 0)
                                                // room for 100 pushes
                                                // without any realloc
   
   
   // Why Vec::new() on page 31 instead of vec![]?
   //
   // Convention.  "empty + will be filled later" reads cleanly with the
   // constructor; the presence of "Vec::new()" makes the empty start
   // visually distinct from "vec![..items..]" with content.  Both compile
   // to identical code.
   
   let mut bins: Vec<Vec<u32>> = Vec::new();
   for size in items {
       // ... bins.push(vec![size]) or bins[i].push(size) inside the loop ...
   }
   
   
   // Practical differences worth knowing:
   //
   //   Vec::new()              const fn — usable in const contexts.
   //                           static EMPTY: Vec<i32> = Vec::new();  ← compiles
   //
   //   vec![]                  macro — not usable in const contexts.
   //                           static EMPTY: Vec<i32> = vec![];      ← error
   //
   //   Vec::with_capacity(n)   empty, but heap-allocates room for n elements.
   //                           Use when you know roughly how big the vec will
   //                           grow, to avoid the doubling reallocations.
   
   
   // All three start at .len() == 0 — the difference is how much heap
   // memory the vec is sitting on:
   Vec::<i32>::new().capacity();              // 0
   vec![1, 2, 3].capacity();                   // typically 3 (or more)
   Vec::<i32>::with_capacity(100).capacity(); // 100