{"schema_version":"4ort.packet/1","entity":{"entity_id":"knapsack-problem","kg_uuid":"b918802c-381d-48c3-a5b7-130bd9f8746c","wikidata_id":"Q864457","name":"knapsack problem","description":"problem in combinatorial optimization","type":"Thing","url":"https://4ort.xyz/entity/knapsack-problem"},"status":"complete","as_of":{"copy_written_at":"2026-11-12T17:30:23Z","last_source_edit_seen":"2026-09-08T18:09:12Z","stale_possible":true,"claims_refreshed_at":null,"source_revision":null},"facts":[{"field":"P31","label":"instance of","value":"optimization problem","value_id":"Q984063","value_raw":"Q984063","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q864457#P31","source_edition":null,"edition_basis":"unknown","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P361","label":"part of","value":"Karp's 21 NP-complete problems","value_id":"Q1734364","value_raw":"Q1734364","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q864457#P361","source_edition":null,"edition_basis":"unknown","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P138","label":"named after","value":"backpack","value_id":"Q5843","value_raw":"Q5843","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q864457#P138","source_edition":null,"edition_basis":"unknown","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P1482","label":"Stack Exchange tag","value":"https://stackoverflow.com/tags/knapsack-problem","value_id":null,"value_raw":"https://stackoverflow.com/tags/knapsack-problem","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q864457#P1482","source_edition":null,"edition_basis":"unknown","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P1889","label":"different from","value":"packing problem","value_id":"Q3851477","value_raw":"Q3851477","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q864457#P1889","source_edition":null,"edition_basis":"unknown","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P2812","label":"MathWorld ID","value":"KnapsackProblem","value_id":null,"value_raw":"KnapsackProblem","rank":"normal","current":null,"qualifiers":[{"field":"P1810","label":"subject named as","value":"Knapsack Problem"}],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q864457#P2812","source_edition":null,"edition_basis":"unknown","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P5047","label":"Rosetta Code page ID","value":"Knapsack_problem","value_id":null,"value_raw":"Knapsack_problem","rank":"normal","current":null,"qualifiers":[{"field":"P9675","label":"MediaWiki page ID","value":"3790"}],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q864457#P5047","source_edition":null,"edition_basis":"unknown","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P5106","label":"Dictionary of Algorithms and Data Structures ID","value":"knapsackProblem","value_id":null,"value_raw":"knapsackProblem","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q864457#P5106","source_edition":null,"edition_basis":"unknown","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P6104","label":"maintained by WikiProject","value":"WikiProject Mathematics","value_id":"Q8487137","value_raw":"Q8487137","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q864457#P6104","source_edition":null,"edition_basis":"unknown","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P6366","label":"Microsoft Academic ID (discontinued)","value":"113138325","value_id":null,"value_raw":"113138325","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q864457#P6366","source_edition":null,"edition_basis":"unknown","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P6564","label":"Brilliant Wiki ID","value":"backpack-problem","value_id":null,"value_raw":"backpack-problem","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q864457#P6564","source_edition":null,"edition_basis":"unknown","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P10374","label":"computational complexity","value":"NP-complete","value_id":"Q215206","value_raw":"Q215206","rank":"normal","current":null,"qualifiers":[{"field":"P518","label":"applies to part","value":"decision problem"}],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q864457#P10374","source_edition":null,"edition_basis":"unknown","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P10374","label":"computational complexity","value":"NP-hard","value_id":"Q1137554","value_raw":"Q1137554","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q864457#P10374","source_edition":null,"edition_basis":"unknown","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P13397","label":"GitLab.com topic ID","value":"knapsack+problem","value_id":null,"value_raw":"knapsack+problem","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q864457#P13397","source_edition":null,"edition_basis":"unknown","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}}],"unknowns":[],"omitted":{"facts":0,"reason":null},"licences":[{"source":"wikidata","source_name":"Wikidata","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"fields":["P31","P361","P138","P1482","P1889","P2812","P5047","P5106","P6104","P6366","P6564","P10374","P13397"]}],"routes":{"entity_page":"https://4ort.xyz/entity/knapsack-problem","packet_api":"https://4ort.xyz/api/v1/entities/knapsack-problem/packet","facts_jsonld":"https://4ort.xyz/entity/knapsack-problem/facts.json","changes_api":"https://4ort.xyz/api/v1/knowledge/get_entity_changes?entity=knapsack-problem","attention_api":"https://4ort.xyz/api/v1/knowledge/get_attention?entity=knapsack-problem","wikidata":"https://www.wikidata.org/wiki/Q864457","official_website":null},"trust_rules":{"wikidata-reference-support/2":"From the references in our copy of the statement: high = it cites a source (stated in P248, or a reference URL that is not Wikipedia); medium = only 'imported from Wikimedia project' or a Wikipedia URL; unscored = our copy holds no reference (older copies dropped references, so this is not evidence that Wikidata has none). Wikidata may hold more references than our copy shows. Reference support, not a probability."},"notes":["Our copy of this item's statements has not been checked against Wikidata since tracking began (2026-10-25); a newer value may exist."]}