We are given a set of $n$ coins with denominations $v_1,v_2,\ldots,v_n$ and a number $x$.

The coins are to be divided between to persons, with the restriction that each person's coins must add up to at least $x$.

For example, if $x=1$, $n=2$, and $v_1=v_2=2$, then there are two possible distributions: one where Person 1 gets coin #1 and Person 2 gets coin #2, and one with the reverse. (These distributions are considered distinct even though both coins have the same denomination.)

I'm interested in counting the possible distributions. I'm pretty sure this can be done in $O(nx)$ time and $O(n+x)$ space using dynamic programming; but I don't see how.

  • $\begingroup$ Are you familiar with the "subset sum" problem? $\endgroup$ – Peter Taylor Nov 22 '18 at 14:17
  • $\begingroup$ @PeterTaylor No, I didn't know that problem. I read it briefly on Wikipedia, but don't see the connection with this problem. $\endgroup$ – geager Nov 22 '18 at 15:10
  • $\begingroup$ It's exactly this problem when $2x = \sum v_i$. $\endgroup$ – Peter Taylor Nov 22 '18 at 15:16
  • $\begingroup$ If you can provide the original url and/or the full text of the problem, you might get much more useful replies. $\endgroup$ – John L. Nov 23 '18 at 3:14

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.