Interview question (constant-time algorithm, ILP)

Question

A juice machine has three buttons small, medium large. Each size adds an amount of juice in a range to the cup. Eg small might add from 10-20 mL, medium from 30-35 mL, large from 40-50 mL. The exact numbers are relatively small (0-1000), integral, and known ahead of time

Input: cup size (mL), amount to fill (mL)

Output: whether or not a sequence of button presses can be constructed that is guaranteed to fill the cup with at least amount_to_fill mL while not overflowing the cup. A different sequence of button presses cannot be performed depending on how much the previous button presses ended up filling the cup, ie the sequence must be fully determined before any of the buttons are pressed.

This trivially reduces to the integer linear programming problem:

Given a,b,c,d,e,f,G (all integers, G very large, the rest relatively small)

maximize: ax+by+cz s.t. dx+ey+fz < G and x,y,z are integers

for which, the maximum can apparently be found in constant time. Denote this maximum M(a,b,c,d,e,f,G). What is the closed-form solution to M?

Answer 1

After glancing at http://www.lume.ufrgs.br/bitstream/handle/10183/66091/000870881.pdf;sequence=1,

I think I figured it out.

Something along the lines of, wlog, let (a,d) have ratio a/d >= b/e >= c/f.

Then y is capped at d/gcf(e,d) and z is capped at d/gcf(f,d). brute force all possible (y,z) possibilities in constant time, fill in the corresponding x=floor[(G-ey-fz)/d] (constant time), and select the maximum ax+by+cz (constant time). QED.

This solution seems a bit inefficient and although there may be a better constant-time solution out there (particularly, for d>100), it scales well for large G which is all that really matters for this question.

Answer 2

Your problem is equivalent to the unbounded knapsack problem(https://en.wikipedia.org/wiki/List_of_knapsack_problems). Hence, I think the problem is NP-Hard. Typically such problems are solved dynamic programming.