AFTD Auto-Formalizing Theoretical Domains

KnapsackAuction.dpSolveList

defimported Lean

A computable dynamic-programming solver for finite 0/1 knapsack instances. The solver processes the agents in the given list order and uses the standard "skip or take" recursion on the remaining capacity. This is the algorithmic counterpart to the abstract welfare-maximizer above, specialized to natural weights, natural capacity, and natural reported values.

Statement

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
open KnapsackAuction in
open scoped BigOperators in
variable {I : Type*} [Fintype I] [DecidableEq I] in
def KnapsackAuction.dpSolveList (w b : I → Nat) : List I → Nat → BinaryAllocation I
Defined in
EconCSLib, `KnapsackAuction.dpSolveList`
Lean proof
By xbei (from the file's git history), from github.com/gametheoryinlean/EconCSLib at 1a88f809b538 (Copyright (c) 2026 EconCSLib contributors. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.30.0.
Verified
08 Oct 2026
Axioms
none listed
Built on 4
Used by 4

Lean source view module on GitHub

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
open KnapsackAuction in
open scoped BigOperators in
variable {I : Type*} [Fintype I] [DecidableEq I] in
/-- A computable dynamic-programming solver for finite `0/1` knapsack instances. The solver processes the agents in the given list order and uses the standard "skip or take" recursion on the remaining capacity. This is the algorithmic counterpart to the abstract welfare-maximizer above, specialized to natural weights, natural capacity, and natural reported values. -/
def KnapsackAuction.dpSolveList (w b : I → Nat) : List I → Nat → BinaryAllocation I
  | [], _ => fun _ => false
  | i :: is, capacity =>
      if w i ≤ capacity then
        let skip := dpSolveList w b is capacity
        let takeTail := dpSolveList w b is (capacity - w i)
        let take := Function.update takeTail i true
        if natBinarySocialWelfare b take ≥ natBinarySocialWelfare b skip then
          take
        else
          skip
      else
        dpSolveList w b is capacity
termination_by items _ => items.length
See it in the graphDiscuss this resultChallenge it