SubsetSum Problem
Greedy algorithm
PROBLEM
In the subsetsum 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).
ALGORITHM
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 worstcase 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
worstcase 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
IMPLEMENTATION
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
call D_QUICKSORT N
X. = 1
do J = 1 to N
if A.J > T then X.J = 0; else T = T  A.J
end
return

COMPARISON
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)
end

I compared the algorithms for solution of the Subsetsum problem and my algorithm
DIOPHANT for solution of the diofantine equations.
Notes:
Subsetsum 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 
CONNECTIONS
Literature
Martello S., Toth P. Knapsack Problems: Algorithms nad Computer Implementations
Chichester, John Wiley & sons 1990