gold = [275960, 286020, 98170, 123800, 413898, 500508, 396133, 231548, 51228, 259666, 31285, 314351, 370736, 682216, 523328, 74440, 793099, 603300, 83550, 678932, 664161, 282154, 385264, 469426, 707269, 316046, 425439, 111463, 763832, 804378] def ExactSubsetSum(S, t): sums = [(0,[])] # keep this list in strictly increasing order for e in S: sums = MergeLists(sums, [(old+e,lis+[e]) for (old, lis) in sums]) sums = [(x,lis) for (x,lis) in sums if x <= t] return sums[-1] def MergeLists(xs, ys): result = [] xs = xs[::-1] ys = ys[::-1] while xs != [] and ys != []: x = xs[-1] y = ys[-1] if x[0] == y[0]: result.append(x) xs.pop() ys.pop() elif x[0] < y[0]: result.append(x) xs.pop() else: result.append(y) ys.pop() result.extend(reversed(xs)) result.extend(reversed(ys)) return result def ApproximateSubsetSum(S, t, epsilon): sums = [(0, [])] # keep this list in strictly increasing order for e in S: sums = MergeLists(sums, [(old+e, lis+[e]) for (old,lis) in sums]) sums = Trim(sums, epsilon/(2*len(S))) sums = [(x,lis) for (x,lis) in sums if x <= t] return sums[-1] def Trim(sums, delta): result = sums[:1] for s in sums[1:]: if s[0] > (1+delta) * result[-1][0]: result.append(s) return result