Hey, I'm given a set $$$S = {a_1, a_2, \dots, a_n}$$$ of integers $$$a_i \leq 10^{5}$$$. I'm also given an integer $$$10^9 \leq W \leq 10^15$$$. I need to tell whether there is an unbounded subset with sum $$$W$$$ (by unbounded I mean that we can use e.g. $$$a_1$$$ few times). The best algorithm I know works in $$$O(nW)$$$ which is obviously too slow. Do you happen to know any algorithm which can solve this problem (maybe randomized one or sth?). Thanks in advance!