Approximate Algorithms for the 0/1 Knapsack Problem 论文
1975Journal of the ACM引用 348
Optimization and Packing ProblemsOptimization and Search ProblemsComplexity and Algorithms in Graphs
摘要
A serms of increasingly accurate algorithms to obtain approximate solutions to the 0/1 one-dlmensmnal knapsack problem :s presented Each algorithm guarantees a certain minimal closeness to the optimal solution value The approximate algorithms are of polynomml time complexity and reqmre only linear storage Computatmnal expermnce with these algorithms is also presented