knapsack problem (optimization version)
GPTKB entity
Statements (32)
| Predicate | Object |
|---|---|
| gptkbp:instanceOf |
mathematical optimization
|
| gptkbp:alsoKnownAs |
gptkb:0-1_knapsack_problem
|
| gptkbp:application |
cryptography
finance resource allocation project selection |
| gptkbp:complexity |
gptkb:NP-hard
|
| gptkbp:field |
gptkb:mathematics
computer science operations research |
| gptkbp:firstDescribed |
19th century
|
| gptkbp:goal |
maximize total value without exceeding weight capacity
|
| gptkbp:hasObjectiveFunction |
maximize sum of values of selected items
|
| gptkbp:hasSpecialCase |
integer programming
resource allocation problem |
| gptkbp:hasVariant |
gptkb:fractional_knapsack_problem
gptkb:multi-dimensional_knapsack_problem gptkb:multi-objective_knapsack_problem |
| https://www.w3.org/2000/01/rdf-schema#label |
knapsack problem (optimization version)
|
| gptkbp:input |
set of items
maximum weight capacity value for each item weight for each item |
| gptkbp:prohibits |
each item can be chosen at most once
total weight ≤ capacity |
| gptkbp:relatedTo |
subset sum problem
knapsack problem (decision version) |
| gptkbp:solvedBy |
dynamic programming
branch and bound greedy approximation |
| gptkbp:bfsParent |
gptkb:NP-hard_problems
|
| gptkbp:bfsLayer |
7
|