Decision problem for unbounded knapsack?

Revision en1, by Dec0Dedd, 2022-06-09 18:17:42

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!

Tags knapsack, algorithms, number theory

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Dec0Dedd 2022-06-09 18:36:04 0 (published)
en1 English Dec0Dedd 2022-06-09 18:17:42 487 Initial revision (saved to drafts)