Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Computing Partitions with Applications to the Knapsack Problem

IP.com Disclosure Number: IPCOM000148215D
Original Publication Date: 1972-Jul-04
Included in the Prior Art Database: 2007-Mar-29
Document File: 52 page(s) / 2M

Publishing Venue

Software Patent Institute

Related People

Horowitz, Ellis: AUTHOR [+3]

Abstract

by Ellis Horowitz and Sartaj Sahni Department of Computer Science Cornell University Ithaca, New York Technical Report No, 72-134 Revised July 4, 1972 I .. ,-" c Coniputing Partitions with Applications . to the Knapsack Problem E. Horowitz and S. Sahni Abstract Given r numbers s1,..,, r , algorithms are in- vestigated for finding all possible combinations of these numbers.which sum to M . This problem is a particular instance of the 0-1 unidimensional knapsack problem. A11 of the usual algorithms for this problem are investi- gated both in terms of asymptotic computing times and storage requirements, as well as average computing times. We develop a technique which improves all of the dynamic programming methods by a square root factor, Using this improvement a variety of new heuristics and improved data structures are incorporated for decreasing the average 1 behavior of these methods, The resulting algorithms are . , -. then compared on a wide set of data. It is then shown how these improvements can be applied to various versions of the knapsack problem

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 9% of the total text.

Page 1 of 52

Computing Partitions with Applications to the
Knapsack Problem

by

Ellis Horowitz and Sartaj Sahni Department of Computer Science Cornell University

Ithaca, New York

Technical Report No,
72-134

Revised July 4, 1972

I

.. -

[This page contains 1 picture or other non-text object]

Page 2 of 52

[This page contains 1 picture or other non-text object]

Page 3 of 52

-

<

/

//

,-"

c

'

Coniputing Partitions with Applications

. to the Knapsack Problem
E. Horowitz and S. Sahni

Abstract

       Given r numbers s1,..,, r , algorithms are in-
vestigated for finding all possible combinations of these
numbers.which sum to M

          . This problem is a particular
instance of the 0-1 unidimensional knapsack problem.

A11 of the usual algorithms for this problem are investi-
gated both in terms of asymptotic computing times and
storage requirements, as well as average computing times.

We develop a technique which improves all of the dynamic
programming methods by a square root factor, Using this
improvement a variety of new heuristics and improved data
structures are incorporated for decreasing the average 1

behavior of these methods, The resulting algorithms are

.

,

- -.

then compared on a wide set of data. It is then shown how
these improvements can be applied to various versions of the
knapsack problem

.

Key.Words and Phrases: partitions, knapsack problem,
dynamic programming, integer optimization

CR Categories: 5-25, 5.39, 5-42.

[This page contains 1 picture or other non-text object]

Page 4 of 52

[This page contains 1 picture or other non-text object]

Page 5 of 52

,

,Computing Partitions with Applications to the Knapsack Problem

E. Horowitz and S. Sahni

Introduction

Given r numbers s , . . ,s we wish t o find all

r

possible combinations of these numbers which sum to M .

This rather simply stated problem is a t the root of several interesting problems in number theory, operations research and polynomial factorization. In the first case it is closely related to the classical number theory study of determining partitions. Phrased in our terminology, deter- mining partitions of M would imply that si = i and
s. = M. So here we are concerned with a more general problem r

than partitions, In [3j, p. 273 Hardy and Wright provide generating functions but no good computational scheme for generating such partitions. If we restrict the si and M

- to be integers and include an additional set of numbers pi then we have an integer programming form of what is usually referred t o as the knapsack problem. In its simplest form one wishes to find the most desirable set of quantities a hiker should pack in his knapsack given a measure of the desirability of each i t e m (pi or profit) subject to its weight (sil and the maximum weight that the 'knapsack can hold (M)

. The partition problem is shown to be a special

* case of the 0-1 unidimensional knapsack problem and it w i l l...