{"slug":"decision-solver-use-x402atlas-com-knapsack-a61ffb","title":"0/1 knapsack solver — exact work-bounded capacity planning and portfolio selecti","host":"decision-solver.use.x402atlas.com","method":"POST","resource":"https://decision-solver.use.x402atlas.com/knapsack","category":"other","description":"0/1 knapsack solver — exact work-bounded capacity planning and portfolio selection for maximum value, with deterministic ties and reproducible DP evidence.","price_listed":0.005,"price_asked":0.005,"state":"answering","state_label":"Answering","checks_7d":1,"answered_7d":1,"latency_ms_median":628,"reported_calls_30d":4,"reported_payers_30d":3,"networks":["eip155:137","eip155:42161","eip155:8453"],"badge":"unverified","paid_checks_7d":0,"paid_ok_7d":0,"example_input":{"body":{"capacity":7,"items":[{"id":"camera","value":4,"weight":3},{"id":"battery","value":5,"weight":4},{"id":"tripod","value":6,"weight":5}]},"bodyType":"json","method":"POST","type":"http"},"output_schema":{"$schema":"https://json-schema.org/draft/2020-12/schema","properties":{"input":{"additionalProperties":false,"properties":{"body":{"additionalProperties":false,"properties":{"capacity":{"description":"Maximum total selected weight; item count times (capacity+1) must not exceed 2,000,000 work units","maximum":100000,"minimum":1,"type":"integer"},"items":{"description":"Unique-ID 0/1 items; each item is considered at most once","items":{"additionalProperties":false,"description":"One 0/1 item selectable at most once","properties":{"id":{"description":"Unique printable-ASCII item identifier","maxLength":64,"minLength":1,"pattern":"^[ -~]+$","type":"string"},"value":{"description":"Non-negative objective value","maximum":1000000000,"minimum":0,"type":"integer"},"weight":{"description":"Positive item weight; items heavier than capacity remain valid but cannot be selected","maximum":1000000000,"minimum":1,"type":"integer"}},"required":["id","weight","value"],"type":"object"},"maxItems":512,"minItems":1,"type":"array"}},"required":["capacity","items"],"type":"object"},"bodyType":{"enum":["json","form-data","text"],"type":"string"},"method":{"enum":["POST"],"type":"string"},"type":{"const":"http","type":"string"}},"required":["type","method","bodyType","body"],"type":"object"},"output":{"properties":{"example":{"additionalProperties":false,"properties":{"_atlas":{"additionalProperties":false,"description":"Atlas documentation and related-route metadata added after deployment","properties":{"docs":{"description":"Documentation URL for this bridge","format":"uri","maxLength":512,"type":"string"},"related":{"description":"Bounded related Atlas routes","items":{"additionalProperties":false,"description":"One related Atlas route","properties":{"bridge":{"description":"Related bridge name","maxLength":64,"type":"string"},"docs":{"description":"Related bridge documentation URL","format":"uri","maxLength":512,"type":"string"},"summary":{"description":"Short capability summary","maxLength":256,"type":"string"},"url":{"description":"Related route URL","format":"uri","maxLength":512,"type":"string"}},"required":["bridge","url","docs","summary"],"type":"object"},"maxItems":3,"type":"array"}},"required":["docs"],"type":"object"},"algorithm_version":{"const":"knapsack-01-dp-v1","description":"Pinned deterministic algorithm and transcript contract","type":"string"},"evidence":{"additionalProperties":false,"description":"Reproducible transcript evidence that detects final-DP drift but does not prove optimality","properties":{"dp_capacity":{"description":"Maximum capacity index in the final DP transcript","maximum":100000,"minimum":0,"type":"integer"},"dp_items":{"description":"Number of item rows incorporated into the final dynamic program","maximum":512,"minimum":0,"type":"integer"},"optimality_proof":{"const":false,"description":"Always false: the digest alone is not an optimality proof","type":"boolean"},"transcript_encoding":{"const":"dpValue[0..capacity] as signed int64 two's-complement, 8-byte big-endian, no prefix","description":"Exact byte encoding hashed; dimensions are carried separately and are not part of the digest","type":"string"},"transcript_sha256":{"description":"Lowercase SHA-256 digest of the encoded final DP values; this is non-proof evidence","maxLength":64,"minLength":64,"pattern":"^[0-9a-f]{64}$","type":"string"},"verification":{"const":"recompute the bounded dynamic program; the digest detects transcript drift but is not an optimality proof","description":"Independent verification instruction; recomputation is required to verify optimality","type":"string"}},"required":["dp_items","dp_capacity","transcript_encoding","transcript_sha256","optimality_proof","verification"],"type":"object"},"objective":{"const":"maximum_total_value","description":"The solver maximizes total selected value within capacity","type":"string"},"objective_value":{"description":"Proven maximum total value","maximum":512000000000,"minimum":0,"type":"integer"},"operation":{"const":"knapsack","description":"Stable route operation name","type":"string"},"optimal":{"const":true,"description":"True because the bounded dynamic program computes the exact optimum","type":"boolean"},"solution":{"additionalProperties":false,"description":"Selected item set and capacity accounting","properties":{"remaining_capacity":{"description":"Capacity minus selected weight","maximum":100000,"minimum":0,"type":"integer"},"selected":{"description":"Selected items in input order; [] is valid when no positive-value item fits","items":{"additionalProperties":false,"description":"One selected item","properties":{"id":{"description":"Input item identifier","maxLength":64,"minLength":1,"pattern":"^[ -~]+$","type":"string"},"original_index":{"description":"Zero-based input index","maximum":511,"minimum":0,"type":"integer"},"value":{"description":"Input item value","maximum":1000000000,"minimum":0,"type":"integer"},"weight":{"description":"Input item weight","maximum":1000000000,"minimum":0,"type":"integer"}},"required":["id","original_index","weight","value"],"type":"object"},"maxItems":512,"type":"array"},"used_capacity":{"description":"Total selected weight","maximum":100000,"minimum":0,"type":"integer"}},"required":["selected","used_capacity","remaining_capacity"],"type":"object"},"warnings":{"description":"Always empty for this exact solver; non-proof semantics are carried in evidence","items":{"description":"Human-readable warning","type":"string"},"maxItems":0,"type":"array"},"work_units":{"description":"Item count times (capacity+1), the declared dynamic-program work units","maximum":2000000,"minimum":0,"type":"integer"}},"required":["operation","algorithm_version","objective","objective_value","optimal","solution","work_units","evidence","warnings"],"type":"object"},"type":{"type":"string"}},"required":["type"],"type":"object"}},"required":["input"],"type":"object"},"history":[{"day":"2026-09-24","reachable":true,"status":402,"valid_402":true,"asked_usdc":0.005,"price_match":true,"latency_ms":628,"error":null}],"description_full":"0/1 knapsack solver — exact work-bounded capacity planning and portfolio selection for maximum value, with deterministic ties and reproducible DP evidence.","last_updated":"2026-09-15T06:32:27.576Z","schemes":["exact"]}