wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

knapsack (485B)

      1 # Knapsack problem
      2 
      3 We have items with weights and values, we want to find the best total value possible while keeping the weight under a certain limit
      4 
      5 It is [np_complete] but not [strongly_np_complete] as there is a [pseudo_polynomial_time] algorithm.
      6 
      7 There is an [fptas]
      8 
      9 Special cases:
     10 - [subset_sum]
     11 - [change_making_problem]
     12 
     13 Generalizations:
     14 - [integer_linear_programming]
     15 - [quadratic_knapsack_problem]
     16 
     17 Up: [decision_problem], [optimization_problem]
     18 
     19 See also: [bin_packing]