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 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:

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

Response:

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

How to call it

MCP

Connect https://computefirst.net/mcp (setup), then call execute with:

{
  "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)

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.

CLI

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

Get the client at /clients/cli/.

Related tools

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