greedy_pack_list
Given a remaining capacity remCap : ℝ and a list of timely items, greedy_pack_list remCap : List TimelyItem → Finset TimelyItem recursively scans the list, returning a Finset TimelyItem containing each item whose size does not exceed the remaining capacity (inserting it into the finset and subtracting its size from the remaining capacity), and skipping items that do not fit.
Statement
noncomputable def greedy_pack_list (remCap : ℝ) : List TimelyItem → Finset TimelyItem
- Defined in
- arXiv:2611.09611, Section 2
- Verified
- 09 Nov 2026
- Axioms
- none listed
- Built on 2
- TimelyItemA structure
TimelyItemrepresenting an item in online timely bin packing, with fieldsid : ℕ(a unique natural identifier),… - instLinearOrderTimelyItemThe linear order on
TimelyItemobtained by pulling back the lexicographic order onℝ ×ₗ ℕ ×ₗ ℝ ×ₗ ℝalong the injective function…
- TimelyItemA structure
- Used by 1
- thrifty_greedy_stepFor a non-empty set of remaining timely items
Rwith witnesshR : R.Nonempty,thrifty_greedy_step R hRreturns theTimelyBinwhose…
- thrifty_greedy_stepFor a non-empty set of remaining timely items
Read back from the Lean
greedy_pack_list is a function that takes a remaining capacity remCap : ℝ and a list of TimelyItems, returning a Finset TimelyItem defined recursively:
- For the empty list [], it returns the empty finset ∅.
- For a cons cell x :: xs, if x.size ≤ remCap, it inserts x into greedy_pack_list (remCap - x.size) xs; otherwise, it returns greedy_pack_list remCap xs.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- Greedily packs a list of items into remaining capacity, returning a finset of packed items. -/ noncomputable def greedy_pack_list (remCap : ℝ) : List TimelyItem → Finset TimelyItem | [] => ∅ | x :: xs => open Classical in if x.size ≤ remCap then insert x (greedy_pack_list (remCap - x.size) xs) else greedy_pack_list remCap xs