---
title: "algorithm-knapsack-rust-approximant — Mova code model"
description: "Mova code model of algorithms/src/knapsack/mod.rs.groupant/rust_approximant.rs: components with their labels, obernants and the model text."
url: "https://groupants.elamur.ai/free/en/mova/algorithms/src/knapsack/mod.rs.groupant/rust_approximant.rs.groupant/"
---
Elamur: [Mova](https://md.mova.elamur.ai/free/en/) · [Dictionary](https://md.dictionary.elamur.ai/free/en/) · [Research](https://md.research.elamur.ai/free/en/) · **Groupants**

This page as HTML: <https://groupants.elamur.ai/free/en/mova/algorithms/src/knapsack/mod.rs.groupant/rust_approximant.rs.groupant/>

# algorithm-knapsack-rust-approximant

The groupant beside algorithms/src/knapsack/mod.rs.groupant/rust_approximant.rs in the Mova repository: what the code computes, what it never does, how to go back from its outputs, its invariants, cost and checks.

## Facts

- **kind:** groupant
- **status:** partial descriptive instance
- **source:** [`algorithms/src/knapsack/mod.rs.groupant/rust_approximant.rs`](https://github.com/ElamurAI/mova-free/blob/main/algorithms/src/knapsack/mod.rs.groupant/rust_approximant.rs)
- **source SHA-256:** `34a3f81d27cf907d…`
- **part of:** [algorithm-knapsack](https://md.groupants.elamur.ai/free/en/mova/algorithms/src/knapsack/mod.rs.groupant/)
- **repository folder:** [`algorithms/src/knapsack/mod.rs.groupant/rust_approximant.rs.groupant`](https://github.com/ElamurAI/mova-free/tree/main/algorithms/src/knapsack/mod.rs.groupant/rust_approximant.rs.groupant)
- **repository commit:** `855da7bd4a7b`

> **Implementation material.** A Mova code model describes this code at one source revision: partial models, finite checks and their stated scope. It is not a reviewed general exposition, and its labels are shown as written, never raised.

## Components

| component | label | where |
|---|---|---|
| **approximant** | partial | [descriptant](#descriptant) |
| **ast** | partial | `syntax.json` |
| **descriptant** | present | [descriptant](#descriptant) |
| **invariant** | partial | `model.md` |
| **tests** | existing checks referenced | [tests](#tests) |

## Obernants

The typed relations around the forward model: the behaviour complement (what the code never does), the reverse reconstruction (every input compatible with an output) and specialised views.

| id | type | label | where |
|---|---|---|---|
| `behavior_complement` | behavior_complement | partial relational specification | [behavior_complement](#behavior-complement) |
| `reverse_reconstruction` | reverse_reconstruction | partial relational specification | [reverse_reconstruction](#reverse-reconstruction) |

## Model text


Migration: consolidated into model.md, 2026-11-04, operator decision; fresh hash-bound references to the former files were rebound to the sections below.

### descriptant

#### Certified knapsack Rust companion

Epoch 2026-10-29. max_value(items, capacity, budget) returns Estimate with value,
upper_bound and used_exact_fallback. Budgets 1/2/5/10% bound relative objective
loss against the exact optimum V; define zero loss when V=0.

Before implementation the prediction was O(n log n) time and O(n) storage on
certified inputs, versus O(nC) exact row work. Failed certificates add sorting
overhead to exact DP. This is a certified heuristic with fallback, not an FPTAS.

The lower value L is the greater of density greedy packing and the best feasible
single item, both including all zero-weight values. Cross products and tie
breaks are exact and deterministic. Only fitting items decrease remaining
capacity. Fractional prefix packing, with its fractional value rounded upward,
gives U. Thus L<=V<=U. Accept only U-L<=floor(pU/100).
This implies L>=(1-p/100)U>=(1-p/100)V. Otherwise call the exact reference.

The certificate computes floor(pU/100) by quotient/remainder decomposition,
avoiding multiplication overflow. On usize<=64 targets slice value totals and
cross products fit u128. No floating point or approximate capacity arithmetic.
The API returns a feasible objective, not selected indices. Large capacities
can succeed without exact row allocation: dimension-error equivalence is not
claimed. Ranking allocation can fail independently of exact row allocation.

Epoch observation: best-single-item fixes greedy tie behavior at usize::MAX.
A zero-weight baseline can admit nonoptimal output without artificial degradation.
Finite tests support the implementation; the inequality supplies its scoped
analytical argument. No Lean proof or semantic AST projection is present.

### models

## Mathematical models

### behavior_complement
Universe: finite item slices, capacity, supported budget and result on usize<=64.
For success exclude value greater than optimum V, upper_bound less than V,
and relative objective loss greater than budget (zero loss when V=0).
A passing certificate excludes used_exact_fallback=true; a reference result
excludes false. Allocation failure is environmental. This is a specification
complement; exhaustive runtime verification is not claimed.

### reverse_reconstruction
For observed (v,u,false), compatible inputs have greedy-or-singleton value v,
fractional rounded upper u, and a passing certificate. For (v,v,true), inputs
have optimum v and a failing certificate. Many multisets and permutations
are compatible. Enumerating finite lists and retaining matching relations
gives bounded preimages; no unbounded reconstruction implementation exists.

### invariant and composition
Each packing step retains nonnegative remaining capacity and distinct selected
indices of total weight capacity-remaining. Fractional density prefix is an LP
upper bound. The combiner joins feasible lower, fractional upper and integer
predicate, selecting certified output or exact reference. Tests exercise both
routes; constituent correctness alone would not establish the wiring.

### cost
Filter O(n), sort O(n log n), scans O(n), storage O(n). Rejected certificate
adds O(n(C+1)) time and O(C+1) memory. Small capacity and weak certificates
may regress. Typed errors have no numerical approximation guarantee.

### Current profiles and classification

Caps 1%, 2%, 5%, 10% use the same integer certificate and exact fallback.
Classification is objective_loss / relaxation_certificate /
per_input_certificate. Bound kind remains analytical: for p<=10,
L>=(1-p/100)U and OPT<=U imply L>=(1-p/100)OPT.
A per-input certificate establishes this premise; finite observed error does
not establish the inequality for unseen inputs.

### tests

#### Evidence, 2026-10-29

Four optimized Rust unit tests pass twice with actual mova-algorithms and
mova-approx libraries. 1,100 deterministic instances (length 0..10, 100 each)
are compared with independently enumerated subsets at all four budgets;
each call is repeated and compared exactly. Loss uses independent integer
arithmetic, not the implementation certificate.

Checks cover empty input, zero optimum, zero-weight u64::MAX, usize::MAX
capacity, arbitrary u128 certificate boundaries, both dispatch routes, and
nonexact output 300 versus optimum 330 accepted for 15/25% only.
A compiled mutant replacing certificate loss by zero was rejected by three
tests before strengthening the independent loss oracle.

Focused timing: 256 equal items weight=value=1000, capacity=100000; rustc -O,
black_box, 3 exact and 3000 approximate calls per budget. Two runs give value
100000 and zero observed loss; checksums 300000 and 300000000 match.
Approximate ns/call by budget 1/5/15/25: 787/788/801/796 then 791/803/788/797.
Exact ns/call: 21483813/19209591/19126045/19167497 then
20012207/19343775/19323867/19230526.
This favorable workload is not representative performance; short calls and
CPU contention limit precision. Temporary standalone timing harness; integrated
harness is owned by parent. No universal runtime claim.

Run through integrated companion harness or rustc --test with extern
mova_algorithms and mova_approx libraries. Finite tests are not universal proof.

##### Current cap epoch, 2026-10-30

The 1/5/15/25 measurements above are historical; the 15/25 profiles are retired.
Current profiles are 1%, 2%, 5%, 10%. Five optimized standalone Rust tests
pass twice against the updated shared contract and unchanged exact algorithm.
The 1,100 fixed-seed instances retain independently enumerated subset optima.
Certificate equivalence is exhaustively checked for 0<=L<=U<=1000 at every
budget, with exact acceptance/rejection boundaries also checked at u128::MAX.
Raw integer and fractional API budgets above 10% are rejected, including the
retired tiers and nonfinite fractions.

The revised nonexact fixture has free value 500, L=600, OPT=630, U=652.
Only 10% certifies it: certificate gap is 52/652 (~7.98%), true loss is
30/630 (~4.76%). Tighter profiles return exact 630. A separate L=60,U=64
fixture checks budget-dependent dispatch without requiring output error.
A compiled zero-loss certificate mutant fails all five tests.
Classification: objective_loss / relaxation_certificate / per_input_certificate.
No new timing or universal speedup is claimed.