The jelly bean box problem

Question

I believe this is a standard graph theory problem, but I am not sure. I am having a lot of trouble with it though. Give it a go

You have n jelly beans. You want to ship them all to a friend. For 1 ≤ i ≤ m, you can buy any number of boxes, where each box can hold Bi jelly beans. The smallest box fits one bean (b1 = 1). Every box you use must be fully packed. Each box costs a dollar. The goal is to ship your beans with the smallest cost. What is the time and space complexity of finding the optimal solution?

Thanks a lot!

Answer 1

I believe what you're describing is equivalent to the Change-making problem.

If the answer to your question is given by the function $p(n)$, then $p$ satisfies the recursion

$$p(n) = 1 + \min_{i=1}^m p(n-b_i),$$ with $p(0) = 0$.

We let $p(x < 0) = \infty$, say, so that we do not consider any values $n-b_i$ which are negative in the above minimum.

Using a dynamic programming solution, you can solve this problem in $O(nm)$ time with $O(\max_i b_i)$ space.