knapsack_opt
def
For an item subset C and budget b, OPT(C) is the maximum additive value v(S) over all subsets S ⊆ C with total size s(S) ≤ b.
Statement
noncomputable def knapsack_opt {m : ℕ} (v : Fin m → ℝ) (s : Fin m → ℝ) (b : ℝ) (C : Finset (Fin m)) : ℝ
- Defined in
- arXiv:2611.12740 Section 3.1
- Verified
- 11 Nov 2026
- Axioms
- none listed
- Built on 1
- additive_valuationThe additive valuation with item values u: a bundle is worth the sum of its items' values.
- Used by 1
- le_knapsack_optEvery budget-feasible subset S of C achieves value at most OPT(C).
Read back from the Lean
Given a number of items m : ℕ, an item value function v : Fin m → ℝ, an item size function s : Fin m → ℝ, a budget b : ℝ, and a subset of candidate items C : Finset (Fin m), knapsack_opt v s b C is defined as the supremum (in ℝ) over all subsets S ⊆ C such that additive_valuation s S ≤ b of the total valuation additive_valuation v S.
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
/-- The optimal knapsack value an agent can obtain from item set C within budget b. -/ noncomputable def knapsack_opt {m : ℕ} (v : Fin m → ℝ) (s : Fin m → ℝ) (b : ℝ) (C : Finset (Fin m)) : ℝ := ⨆ (S : {S : Finset (Fin m) // S ⊆ C ∧ additive_valuation s S ≤ b}), additive_valuation v S.val