Is this a better way to solve the subset sum?

Question

I was trying a basic way to solve a subset sum problem faster and I came up with this

The naive way is the oldSS function, which tests all 2^n combinations. But then I noticed that, before checking each case, calculate the min and max value possible for the current scenario, and if the target lies in side that range, and it could potentially be a solution there, so only then execute the scenario. This is the newSS function. I was testing the times, and it gave me this

9.91289400371 0.00154754789233

I could further improve the newSS time by caching the getMinMax values into a global variable. However for the naive approach, the time can be improved to 2^(n/2) using a clever hack that cuts the initial list by 2 and then doing the naive approach on each and then comparing the two generated lists.

But compared to the 2^(n/2) running time, does anyone know how well the newSS function does?

Thanks

import timeit from random import randint def oldSS(lst, acc, target): if lst: return oldSS(lst[1:], acc+lst[0], target) or oldSS(lst[1:], acc, target) return acc==target def randomList(): l = [] for i in range(20): l.append(randint(0,1000)) return l def getMinMax(lst): mi = 0 mx = 0 for i in lst: if i < 0: mi += i elif i > 0: mx += i return (mi, mx) def newSS(lst, acc, target): if lst: a = False b = False mimx = getMinMax(lst[1:]) nmi = acc+lst[0] + mimx[0] nmx = acc+lst[0] + mimx[1] if target >= nmi and target <= nmx: a = newSS(lst[1:], acc+lst[0], target) nmi = acc + mimx[0] nmx = acc + mimx[1] if target >= nmi and target <= nmx: b = newSS(lst[1:], acc, target) return a or b return acc==target if __name__ == '__main__': print timeit.timeit('oldSS(randomList(), 0, 60)', number=10, setup="from __main__ import oldSS,randomList") print timeit.timeit('newSS(randomList(), 0, 60)', number=10, setup="from __main__ import newSS,getMinMax,randomList")

I think they should be the same. I tried it with like ` r = randomList() print oldSS(r, 0, 60) print newSS(r, 0, 60)` and ` r = randomList() print oldSS([1,2,3], 0, 6) print newSS([1,2,3], 0, 6)` and it gave the same answers. — omega
– omega, Commented May 8, 2016 at 22:50

infiniteRefactor · Accepted Answer · 2016-05-08 22:58:18Z

Your new approach is called branch and bound and analyzed in the study of algorithms and complexity theory in a great detail.

Branch and bound is known to decrease best case complexity of the problems. However worst case never changes. Think about a collection of numbers where lower and upper bounds of subtotals are very close to the target. In that case you can not prune any meaningful part of the search space. On average case you can improve running time significantly. Calculating the exact average case complexity of a branch and bound algorithm is a little bit hard, since branch and bound methods are very sensitive to input distribution. My educated but a bit rusty guess is the complexity of your new algorithm won't be lower then O(2^n/2).

If you need a scientific answer on the asymptotic computational complexity I'd recommend doing some research or you can ask the question on CS stack exchange. If you're just trying to understand which approach works better, you can set up empirical trials to compare them. Such a trial would be best practical approach.

Collectives™ on Stack Overflow

Is this a better way to solve the subset sum?

1 Answer 1

Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Related