---
title: "algorithm-knapsack-tests — Mova code model"
description: "Mova code model of algorithms/src/knapsack/tests.rs: components with their labels, obernants and the model text."
url: "https://groupants.elamur.ai/free/en/mova/algorithms/src/knapsack/tests.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/tests.rs.groupant/>

# algorithm-knapsack-tests

The groupant beside algorithms/src/knapsack/tests.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/tests.rs`](https://github.com/ElamurAI/mova-free/blob/main/algorithms/src/knapsack/tests.rs)
- **source SHA-256:** `3b69463b42d2642d…`
- **repository folder:** [`algorithms/src/knapsack/tests.rs.groupant`](https://github.com/ElamurAI/mova-free/tree/main/algorithms/src/knapsack/tests.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 | [approximant](#approximant) |
| **ast** | partial | `syntax.json` |
| **descriptant** | present | [descriptant](#descriptant) |
| **invariant** | partial | [approximant](#approximant) |
| **tests** | existing checks referenced | [checks](#checks) |

## 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 source derived model | [behavior_complement](#behavior-complement) |
| `reverse_reconstruction` | reverse_reconstruction | partial source derived model | [reverse_reconstruction](#reverse-reconstruction) |
| `independent_oracle` | independent_oracle | partial source derived model | [independent_oracle](#independent-oracle) |
| `property_assumptions` | property_assumptions | partial source derived model | [property_assumptions](#property-assumptions) |
| `bounded_coverage_cost` | bounded_coverage_cost | partial source derived model | [bounded_coverage_cost](#bounded-coverage-cost) |

## Model text


### descriptant

#### knapsack test groupant

Epoch 2026-10-29: prospective expectations were saved outside the repository
before extraction. Existing inline tests were moved; two new tests extend
coverage. Production source prefix remained byte-identical. The new fixtures
passed twice and a specifically filtered NEW test rejected a compiled semantic
source mutant. Exact domains, assumptions and limitations are in models.md.

Combiner: source identity plus oracle construction plus assertion wiring form
a conditional finite-check model. Typed models answer separate questions; no
additive inverse identity is assumed. Syntax is partial, macros opaque.
A passing test does not establish parent wiring or full-domain correctness.

### approximant

#### Forward, invariant and cost

Generate deterministic fixtures, compute the independently structured oracle,
compare production output, and fail on disagreement. Property loops hold their
listed assumptions fixed while changing order, padding, or a third sequence.
Invariant: each checked fixture has its reference computed without consulting
the output being tested; seeds advance by explicit wrapping arithmetic.
The models.md bounded_coverage_cost section gives algorithm-specific costs.
Assertion execution supplies bounded evidence; it does not prove the production
recurrence, all inputs, or source correctness from sidecar validity.

### models

## Knapsack test models

Subject: tests.rs at manifest SHA; observation: one test invocation. Assume
ordinary supported usize, successful small allocations, and fixed item values.
These are partial source-derived models with bounded runtime evidence.

### behavior_complement

Universe U=(items,C,proposed result,verdict). Let V be the subset-enumerated
maximum. Pass with result!=Ok(V) is absent from successful oracle assertions.
The exceptional dimension tests separately exclude successful allocation for
overflowing dimensions. This is an exact assertion-graph complement slice,
not a claim every wrong implementation is detected. A new larger-subset test
rejects ascending capacities, which permit repeated positive-weight items.

### reverse_reconstruction

For observed failing fixture/output, compatible implementations are all maps
producing that output there. Passing outputs retain all implementations equal
to V on the sampled domain. Several defects can share the same wrong value;
no unique defect or source reconstruction is implied. The compiled ascending
loop gives an executed member of the failure fiber.

### independent_oracle

Enumerate all masks of item indices, sum selected weights and u128 values,
then maximize feasible totals. No dynamic-programming row is reused.
Old tests check 44,286 cases. New twelve-item fixtures check 256 cases and
1,048,576 masks; capacity/permutation fixtures add 544 oracle cases and 139,264
masks. Bounded generated weights guarantee oracle usize sums cannot overflow.
The separate usize::MAX overweight witness uses a hand-derived result, avoiding
that oracle outside its safe-weight domain.

### property_assumptions

Permuting item indices preserves V and increasing capacity cannot decrease V,
provided values/weights are unchanged and each index is independently selectable
once. Reverse plus rotation exercises order changes; 32 eight-item lists at
capacities 0..16 check equality and adjacent monotonicity against subset values.
Zero-weight items are distinct selectable entries, including repeated values.

### bounded_coverage_cost

64 seeded twelve-item lists include zero weights and values near u64::MAX;
capacities are 0,1,7,15. A separate overweight usize::MAX item must be skipped.
The second family has 32 deterministic eight-item lists and 17 capacities.
Oracle work O(2^N*N), space O(N); DP O(N*(C+1)) time/O(C+1) space.
No huge allocation, exhaustive large-item search or allocator-failure injection.

### checks

#### Evidence, 2026-10-29

Cargo crate library suite passed twice, single-threaded: 36 tests at this branch.
This file adds two tests to its preserved old suite. Strict Clippy on all crate
targets and cargo fmt --check passed. External scratch compiled a changed
production source with this exact test file; a filtered new test failed with
exit 101. KMP reset overlap fallback, Levenshtein doubled substitution cost,
and knapsack used ascending capacities. Only the respective mutant applies
to each file. No mutated code is committed. See models.md for exact coverage.

Repeated output comparison excludes Cargo build lines and elapsed-time footer.
Wall time is not an algorithm benchmark. New checks remain deterministic and
bounded, and no full input-space proof or allocation-failure coverage is claimed.