The Knapsack Problem: A Survey

Authors

Harvey M. Salkin
Cornelis A. De Kluyver

Document Type

Report

Publication Date

12-1-1972

Abstract

A unifying survey of the literature related to the knapsack problem; that is, maximize Σᵢvᵢxᵢ, subject to Σᵢwᵢxᵢ ≤ W, xᵢ ≥ 0, and xᵢ integer; where vᵢ, wᵢ and W are known positive integers. Various uses, including those in group theory and in other integer programming algorithms, as well as applications from the literature, are discussed. Dynamic programming, branch and bound, search enumeration, heuristic methods, and other solution techniques are presented. Computational experience, and extensions of the knapsack problem, such as to the multi-dimensional case, are also considered.

Keywords

Operations research, Knapsack problem (Mathematics), Integer programming, Dynamic programming, Combinatorial optimization, Algorithms

Publication Title

Technical Memorandums from the Department of Operations, School of Management, Case Western Reserve University

Issue

Technical memorandum no. 281

Rights

This work is in the public domain and may be freely downloaded for personal or academic use

Recommended Citation

Salkin, Harvey M. and De Kluyver, Cornelis A., "The Knapsack Problem: A Survey" (1972). Research Reports from the Department of Operations. 268.
https://commons.case.edu/wsom-ops-reports/268