# Value ties in a five-item knapsack

KL-FCS-044 · Combinatorial optimization · version 1.0.0

## Problem

Maximize total item value without exceeding the weight capacity.

## Context

Separate a feasible chosen subset from a certified best objective over all allowed choices.

## Definitions

- **0/1 knapsack**: Each item may be chosen at most once under a total weight limit.
- **Primal witness**: A concrete feasible subset attaining a particular value.
- **Optimality**: No other feasible subset has a larger objective.

## Checked result

Maximum value: 15.

Each subset is a distinct candidate. The checker independently computes feasibility and objective, accepts any optimal witness, and rejects attractive but overweight selections.

## Checker reasoning

1. Enumerate every binary item-selection vector.
2. Discard selections exceeding capacity.
3. Compute each remaining total value.
4. Check that the submitted subset is feasible and attains the maximum.

## Dataset construction

{
  "family": "combinatorial-optimization",
  "task": "Maximize total item value without exceeding the weight capacity.",
  "input_encoding": "Structured JSON; field meanings are stated in the specification.",
  "coverage": "Complete subset enumeration · 32 candidates",
  "acceptance": [
    "Enumerate every binary item-selection vector.",
    "Discard selections exceeding capacity.",
    "Compute each remaining total value.",
    "Check that the submitted subset is feasible and attains the maximum."
  ],
  "generation": "Deterministic finite fixture; full enumeration or witness replay as stated.",
  "split_policy": "Reference corpus for exposition and reproduction; no train/test evaluation split is claimed."
}

## Formal payload

```json
{
  "specification": {
    "items": [
      [
        1,
        2
      ],
      [
        2,
        4
      ],
      [
        3,
        4
      ],
      [
        4,
        6
      ],
      [
        5,
        9
      ]
    ],
    "capacity": 8,
    "item_encoding": "[weight, value]; index identifies an indivisible item"
  },
  "claim": {
    "maximum_value": 15
  },
  "witness": {
    "selected": [
      0,
      1,
      4
    ]
  }
}
```

## Complexity

n items produce 2ⁿ subsets. Pseudopolynomial dynamic programming offers a different tradeoff for integral capacity.

## Limits

Only this finite 0/1 instance is certified; no approximation ratio or measured solver speed is claimed.

## Common error and further work

The highest value-to-weight ratio can fail for indivisible 0/1 items.

Add assignment dual certificates, set cover, and branch-and-bound proof logs.

## Verification

Complete subset enumeration · 32 candidates. 32 checker units.
Replay with `python3 tools/verify.py`. Mechanical status: checked; human review
has not yet been recorded. Custom Python verification, not a proof-assistant
claim. Checker 1.0.0 and exact source hashes are in `verification.json`.

## Provenance and references

Original Kenton Labs reference instance, authored with Codex assistance on 2026-10-11.
No external dataset or model-generation experiment. Reuse-license selection
remains pending.

- [Conceptual reference](https://developers.google.com/optimization/assignment/linear_assignment)