Subset-Sum Problem
Greedy algorithm

In the subset-sum problem we wish to find a subset of A.1,...,A.N whose sum is as large as possible but not larger than T (capacity of the knapsack).

Greedy algorithm is an approximate algorithm, which consists in examining the items and inserting each new item into the knapsack if it fits. Better average results can be obtained by sorting items according to decreasing weights. The time complexity is O(N*lg N) but the worst-case performance ratio is 1/2. Martello and Toth define this concept: Let A. be an approximate algorithm for a given maximization problem. For any instance I of the problem, let OPT.I be the optimal solution value and A.I the value found by A.; then, the worst-case performance ratio of A. is defined as the largest real number R.A such that

(A.I/OPT.I)>=R.A for all instances I

Unit: internal subroutine
Global variables: array A.1,...,A.N of positive integers, output array X.
Parameters: a positive integer N, a positive integer T
Interface: D_QUICKSORT - sorting in descending order
Result: output array X., where X.J=1 if item A.J is selected; or X.J=0 otherwise (for J=1,...,N)

GS: procedure expose A. X.
parse arg N, T
X. = 1
do J = 1 to N
  if A.J > T then X.J = 0; else T = T - A.J


For N=100;T=25557 and the array A. created by statements:

Seed = RANDOM(1, 1, 481989)
do J = 1 to N
  A.J = RANDOM(1, 1000)

I compared the algorithms for solution of the Subset-sum problem and my algorithm DIOPHANT for solution of the diofantine equations.

I halted the EXACT_SUBSET_SUM after 30 minutes of computations. For APPROX_SUBSET_SUM I used the value Epsilon=0.5


Subset-sum problem - Comparison of Algorithms
Algorithm Subset sum Seconds
GS 25554      0.05 
DPS 25557   240.24 
APPROX_SUBSET_SUM 25436    12.31 
DIOPHANT 25557      0.82 



Martello S., Toth P. Knapsack Problems: Algorithms nad Computer Implementations
Chichester, John Wiley & sons 1990

cover contents index main page

last modified 8th August 2001
Copyright 2000-2001 Vladimir Zabrodsky
Czech Republic.