AFTD Auto-Formalizing Theoretical Domains

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
See it in the graphDiscuss this resultChallenge it