Polynomial-time approximation 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).
This algorithms is evolved from Exponential-time exact algorithm. We use a trimming parametr Delta such that 0<Delta<1. To "trim" a list L. by Delta means to remove as many elements from L. as possible, in such a way that for every element Y that was removed from L. there is an element Z<=Y in L. such that (Y-Z)/Y<=Delta. The element Z is representing Y in the new list. Cormen, Leiserson and Rivest credit O. H. Ibarra and Ch. E. Kim with inventing the APPROX_SUBSET_SUM function.
Unit: internal function
Global variables: array A.1,...,A.N of integers, array A. is not changed
Parameters: a positive integer N, a positive integer T, a real Epsilon (0<Epsilon<1)
Returns: good approximation of largest sum of subset <=T, for any instance of the Subset-sum problem (O-GA)/O<=Epsilon, where O is the optimal solution value and GA the value returned of APPROX_SUBSET_SUM
For N=100;T=25557 and the array A. created by statements:
I compared the algorithms for solution of the Subset-sum problem and my algorithm DIOPHANT for solution of the diophantine equations.
I halted the EXACT_SUBSET_SUM after 30 minutes of computations. For APPROX_SUBSET_SUM I used the value Epsilon=0.5
Exponential-time exact algorithm
Exact algorithm - dynamic programming
Diophantine linear equation
Cormen T. H., Leiserson Ch. E., Rivest R. L. Introduction to Algorithms
The MIT Press, Cambridge, 1990