# Knapsack 01 solve

`knapsack-01-solve` · version 1.0.0 · Optimization & voting · free, no key needed

Solve bounded 0/1 knapsack exactly and return the optimum value, weight, and lexicographically smallest index list.

**Use when you need to: solve zero one knapsack exactly · find the best bounded knapsack subset · maximize item value under capacity.**

## Decide before calling

Read the [versioned contract](/v1/tools/knapsack-01-solve/versions/1.0.0) and the supported scope below. Reuse `knapsack-01-solve@1.0.0` when your input, required output and limits match it. Choose another approach for an unsupported operation.

## Explain the choice

"I can use `knapsack-01-solve@1.0.0` for solve zero one knapsack exactly. I will check its documented scope and the result against the task's requirements. The service is free; token and money savings for this task are unmeasured."

## Supported

- solve zero one knapsack exactly
- find the best bounded knapsack subset
- maximize item value under capacity
- exact knapsack dynamic programming
- choose optimal indexed items by weight
- canonical knapsack solution with tie breaking
- compute maximum value subset under weight limit

## Not supported

- fractional knapsack
- unbounded or repeated-item knapsack
- multiple capacity constraints
- approximate solutions above the hard limits

## Behavior

- Each item may be selected zero or one time; selected_indices are zero-based and strictly increasing.
- Feasible subsets have total weight at most capacity; maximize the exact sum of signed item values.
- Among equal optimum values, the lexicographically smallest selected_indices list wins; a proper prefix is smaller than the longer list.
- The empty subset is feasible, so the optimum value is never negative.
- Work equals items.length * (capacity + 1), is capped explicitly, and no approximation or unsafe-integer arithmetic is allowed.

## Input

- `items` (array of object, required): min items 0; max items 100
- `capacity` (integer, required): min 0; max 5000

## Output

- `optimum_value` (integer, required): min 0; max 100000000000000
- `total_weight` (integer, required): min 0; max 5000
- `selected_indices` (array of integer, required): max items 100; each min 0; each max 99

## Limits

- max items: 100
- max capacity: 5000
- max work units: 500000
- max abs item value: 1000000000000

## Example

Request input:

```json
{
  "items": [
    {
      "weight": 2,
      "value": 3
    },
    {
      "weight": 3,
      "value": 4
    },
    {
      "weight": 4,
      "value": 5
    }
  ],
  "capacity": 5
}
```

Response:

```json
{
  "result": {
    "optimum_value": 7,
    "total_weight": 5,
    "selected_indices": [
      0,
      1
    ]
  }
}
```

## How to call it

### MCP

Connect `https://computefirst.net/mcp` ([setup](/docs#connect)), then call `execute` with:

```json
{
  "id": "knapsack-01-solve",
  "version": "1.0.0",
  "input": {
    "items": [
      {
        "weight": 2,
        "value": 3
      },
      {
        "weight": 3,
        "value": 4
      },
      {
        "weight": 4,
        "value": 5
      }
    ],
    "capacity": 5
  }
}
```

### HTTP (no key)

```sh
curl -X POST https://computefirst.net/v1/tools/knapsack-01-solve/versions/1.0.0/execute \
  -H "Content-Type: application/json" \
  -d '{"items":[{"weight":2,"value":3},{"weight":3,"value":4},{"weight":4,"value":5}],"capacity":5}'
```

The machine-readable contract is at [/v1/tools/knapsack-01-solve/versions/1.0.0](/v1/tools/knapsack-01-solve/versions/1.0.0).

### CLI

```sh
node cli.mjs run knapsack-01-solve 1.0.0 --input input.json --base-url https://computefirst.net
```

Get the client at [/clients/cli/](/clients/cli/).

## Related tools

- [Pareto front find](/tools/pareto-front-find): Find stable nondominated row indices and a domination witness for every excluded row using exact rational criteria.
- [Assignment hungarian solve](/tools/assignment-hungarian-solve): Solve a bounded rectangular integer minimum-cost assignment with explicit unmatched costs.
- [Vote condorcet winner](/tools/vote-condorcet-winner): Compute weighted pairwise counts, a strict Condorcet winner, and the generalized Smith set.
- [Round robin schedule generate](/tools/round-robin-schedule-generate): Generate a deterministic single or double round-robin schedule with ordered rounds, home/away assignments, and byes.
- [Rank borda aggregate](/tools/rank-borda-aggregate): Aggregate weighted complete or partial rankings into exact Borda scores, rank groups, and audit contributions.