# Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems

Original Publication Date: 1974-Dec-31

Included in the Prior Art Database: 2005-Sep-16

## Publishing Venue

Software Patent Institute

## Related People

Oscar H. Ibarra: AUTHOR [+4]

## Abstract

Given a positive integer M and n pairs of positive integers [Equation ommitted] maximize the sum Ed ipi subject to the constraints [Equation ommitted] This is the well known 0/1 knapsack problem. An algorithm is presented which finds for any [Equation ommitted] where P* is the desired optimal sum. Moreover, the algorithm runs in time [Equation ommitted] are functions depending only on s . Thus, for a fixed error, the algorithm has time complexity 4(nlogn) and space complexity 0(n). Hodificatioa of the algorithm for the general knapsack problem where the di's can be any non-negative integer results is a 0(u(e)n) computing time. A linear-time algorithm is also obtained for a special class of 0/1 knapsack problems having the property that pi/ci is the same for all [Equation ommitted]

**This text was extracted from a PDF file.**

**This is the abbreviated version, containing approximately 14% of the total text.**

__Page 1 of 20__THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

**Fast Approximation Algorithms for the Knapsack and Sum of Subset
Problems **

By

Oscar H. Ibarra and Chul E. Kim

Computer, Information, and Control Sciences Institute of Technology University of Minnesota Minneapolis, Minnesota 55455

0400163 11 1- Tecaica~.~Report 74-13 June, 1974 E. Rim This research teas supported by the National Science Foundation Grant GJ-35614. Cover courtesy of Ruth and Jay Leavitt Fast Approximation Algorithms for the Knapsack and Sum of Subset Problemst by Oscar H. Ibarra and I;hul E. Kim Department of Computer Science University of Minnesota Minneapolis, Minnesota 55455

**Abstract **

Given a positive integer M and n pairs of positive integers

(Equation Omitted)

maximize the sum Ed ipi subject to the constraints

(Equation Omitted)

This is the well known 0/1 knapsack problem. An algorithm is presented which finds for any

(Equation Omitted)

where P* is the desired optimal sum. Moreover, the algorithm runs in time

(Equation Omitted)

are functions depending only on s . Thus, for a fixed error, the algorithm has time complexity 4(nlogn) and space complexity 0(n). Hodificatioa of the algorithm for the general knapsack problem where the di's can be any non-negative integer results is a 0(u(e)n) computing time. A linear-time algorithm is also obtained for a special class of 0/1 knapsack problems having the property that pi/ci is the same for all

(Equation Omitted)

Key Words: Knapsack problem, sum of subset; problem, polynomf.ally complete problem, polynomial time-bounded Turing machine, approximation algorithm.

t This research was supported by the National Science Foundation Grant GJ-35614.

**1. Introduction **

University of Minnesota Page 1 Dec 31, 1974

__Page 2 of 20__Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems

A well known combinatorial problem that finds applications to capital bud-geting problems [B], loading problems, and solutions of large optimization problems is the knapsack problem. A simplified version, known as the 0/1 knapsack problem, can be stated as follows: Given a positive integer M and a multiaetl Q consisting of n pairs of positive integers

(Equation Omitted)

maximize the sum Edipi subject to the constraints

(Equation Omitted)

may be interpreted as the profit and weight associated with the i-th-object which can be put into a knapsack whose total weight capacity is M . Throughout the paper we shall arsaumo, with no loss of generality, that each ci < M. Several algorithms have been introduced forsolving the 0/1 knapsack problem, i.e., for,fin;3lag the optimal sum, f* (see, e.g., [2,a,6,7,a;.)* However, all of these algorithms have a worst case computing time which is , exponential in n (the somber of pairs in Thus, these algorithms are only practical. for small values of n . It would indeed be interacting to develop a polynomial time algorithm to solve the knapsack problem. However, it is generally believed that such an...