Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
Citations Over TimeTop 1% of 1975 papers
Abstract
Given a positive integer M and n pairs of positive integers (p~, cD, , (p. , c.), maximize the sum~ ~p~ subject to the constramts~ ~c, < M and ~, = 0 or 1 This is the well-known 0/1 knapsack problem An algorithm is presented which finds for any 0 < e < 1 an approximate solution P satisfying (P* -P)/P* < ~, where P* is the desired optimal sum Moreover, for any fixed e, the algorithm has time complexity 0(n log n) and space complexity O(n) Modification of the algorithm for the unbounded knapsack problem where the ~,'s can be any nonnegative integer results in a O(n) computing time A hnear-time algorithm is also obtained for a special class of 0/1 knapsack problems having the property that p,/c, is the same for all 1 < z < n KEY WORDS AND PHRASES.
Related Papers
- → The Multiple-Choice Knapsack Problem(2004)94 cited
- → STATIC STOCHASTIC KNAPSACK PROBLEMS(2015)4 cited
- → The Stochastic Knapsack(1995)2 cited
- A Summary of Genetic Algorithm on 0/1 Knapsack Problem(2013)
- KNAPSACK: Stata module to solve the knapsack problem(2019)