Knapsack Problems: Algorithms and Computer ImplementationsHere is a state of art examination on exact and approximate algorithms for a number of important NP-hard problems in the field of integer linear programming, which the authors refer to as ``knapsack.'' Includes not only the classical knapsack problems such as binary, bounded, unbounded or binary multiple, but also less familiar problems such as subset-sum and change-making. Well known problems that are not usually classified in the knapsack area, including generalized assignment and bin packing, are also covered. The text fully develops an algorithmic approach without losing mathematical rigor. |
Contents
Bounded knapsack problem | 81 |
Subsetsum problem | 105 |
Changemaking problem | 137 |
Copyright | |
5 other sections not shown
Common terms and phrases
0-1 knapsack problem according algorithm applying approximate approximate algorithms approximation scheme arrays assigned assume average begin end branch-and-bound capacity complexity computed condition considered continuous corresponding current solution decreasing defined described determine dominates dynamic programming error exact Example execution exists fact feasible solution Figure Fortran given gives Hence heuristic implementation improved included increasing initial input inserted instance integer item types iteration knapsack problem least length limit lower bound Martello and Toth maximize minimization multipliers node Note obtained optimal solution value otherwise output parameters positive possible presented procedure produced profit proved reduction relaxation respectively satisfy seconds Section selected single solve sorting Step subset Table Theorem U₁ uniformly random upper bound variables vector weight worst-case performance