2
$\begingroup$

Given an array of $n$ integers $A$, and some value $m$, determine if it is possible, by using certain amounts of each element, to get a total sum equal to $m$. Consider that you can use any amount of any of the elements.

This is sort of like the subset sum problem, but in this case that sum can contain elements multiplied by some factor, and this factor has no upper-bound. I'm struggling quite a bit with this problem, so does anyone know how can I solve it?

$\endgroup$
  • 1
    $\begingroup$ Have you tried proving that this problem is NP-complete? $\endgroup$ – Yuval Filmus Apr 29 '18 at 16:01
  • $\begingroup$ No, but i don´t think it is because this is an exercise in my competitive programming class. Either that or i´m misinterpreting the problem. $\endgroup$ – Mateus Buarque Apr 29 '18 at 16:04
  • 1
    $\begingroup$ If you're allowed to use negative integer amounts, then the problem is easy. Otherwise, I believe that it's NP-complete. You can try adapting the dynamic programming algorithm to solve it for small $m$. $\endgroup$ – Yuval Filmus Apr 29 '18 at 16:05
  • 1
    $\begingroup$ You can reduce your problem to the usual subset sum by replacing each integer $k$ by $k,2k,4k,\ldots,2^{\lfloor \log_2 m \rfloor}k$, and now use any technique you know for subset sum (dynamic programming, meet in the middle) in order to solve your problem. $\endgroup$ – Yuval Filmus Apr 29 '18 at 18:32
  • 1
    $\begingroup$ It's also not quite clear what your goal is, as you pretty much only state the problem. Do you want to give and algorithm or analyse the complexity? What have you tried and where did you get stuck? $\endgroup$ – Raphael Apr 29 '18 at 20:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.