Skip to content

Instantly share code, notes, and snippets.

# jperras/approximate_subset_sum.py Last active Dec 16, 2017

Approximate Subset Sum
 # -*- coding: utf-8 -*- import itertools import operator def trim(data, delta): """Trims elements within `delta` of other elements in the list.""" output = [] last = 0 for element in data: if element['value'] > last * (1 + delta): output.append(element) last = element['value'] return output def merge_lists(m, n): """ Merges two lists into one. We do *not* remove duplicates, since we'd like to see all possible item combinations for the given approximate subset sum instead of simply confirming that there exists a subset that satisfies the given conditions. """ merged = itertools.chain(m, n) return sorted(merged, key=operator.itemgetter('value')) def approximate_subset_sum(data, target, epsilon): """ Calculates the approximate subset sum total in addition to the items that were used to construct the subset sum. Modified to track the elements that make up the partial sums to then identify which subset items were chosen for the solution. """ acc = [{'value': 0, 'partials': }] count = len(data) # Prep data by turning it into a list of hashes data = [{'value': d, 'partials': [d]} for d in data] for key, element in enumerate(data, start=1): augmented_list = [{ 'value': element['value'] + a['value'], 'partials': a['partials'] + [element['value']] } for a in acc] acc = merge_lists(acc, augmented_list) acc = trim(acc, delta=float(epsilon) / (2 * count)) acc = [val for val in acc if val['value'] <= target] return acc[-1] if __name__ == "__main__": data = [650, 1200, 1350, 450, 2875, 1625, 1500, 1875] target = 3450 epsilon = 0.2 print "input: {data}; target: {target}; epsilon: {epsilon}".format( data=data, target=target, epsilon=epsilon) print approximate_subset_sum(data, target, epsilon=epsilon)
to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.