Python implementation of the fast approximation subset sum algorithm from Przydatek, 2002.

Home   »   Python implementation of the fast approximation subset sum algorithm from Przydatek, 2002.

import numpy as np

def error(target, solution, data):
return target - sum(data[solution])

def przydatek_approx_subset(data, target, trials, key=lambda x:x):
'''
Przydatek, B. (2002), A Fast Approximation Algorithm for the Subset‐sum Problem.
International Transactions in Operational Research, 9: 437-459. https://doi.org/10.1111/1475-3995.00366
'''
arr = np.array([key(x) for x in data])
n = len(arr)
best = np.zeros(n, dtype=bool)

for _ in range(trials):
# random selection phase
solution = np.zeros(n, dtype=bool)
r = list(range(n))
np.random.shuffle(r)
for i in r:
if arr[i] <= error(target, solution, arr):
solution[i] = 1

# local improvement phase
indices = [i for i in range(n) if solution[i] == 1]
np.random.shuffle(indices)
for i in indices:
if error(target, solution, arr) == 0:
break

replacements = [arr[l] for l in range(n) if solution[l] == 0 and
0 < (arr[l] - arr[i]) and (arr[l] - arr[i]) <= error(target, solution, arr)]

if len(replacements) > 0:
k = np.where(arr == max(replacements))
solution[k] = 1
solution[i] = 0

# update best solution phase
if error(target, solution, arr) < error(target, best, arr):
best = solution
if error(target, best, arr) == 0:
break

return [x for x, i in zip(data, best) if i]