Strategy to find the most money to use.

Question

As a reward for a week of good behavior, Tommy was given 7 dollars to spend at the canteen. By the time Tommy got to the canteen, there were only chocolate bars, meat pies and pizza pieces left. The prices of a chocolate bar, a meat pie and a pizza piece were 0.75, 1.05 dollars and 1.65 dollars respectively. What is the largest amount Tommy could spend?

I attempted this problem by simply trial and error. So, I said that I he will use 2 x 1.65, 2 x 1.05 and 2 x 0.75. This adds up to be 6.90 dollars. Which was my answer.

I was wondering whether there is a more efficient strategy to do such problems (maybe Diophantine equations).

Help would be appreciated.

Thank you :)

Answer 1

the maximum common divisor of the coins is $15$ cents so the best you can strive for is $15\cdot46$ cents which is actually $6.90$ dollars. You already proved it is possible.

In general this is a hard problem, look up the frobenius coin problem in google.

Answer 2

This is an example of the knapsack problem, a notorious group of combinatorics/optimisation problems, for which there are algorithms and approaches that are the best and fastest for varying constraints but none that give the best solution in the fastest time for all problems.

In particular your problem is a discrete or classic knapsack problem: one in which the number of each object must have an nonnegative integer value - that is, you can't have "half a chocolate bar" or "minus two pies". The weight of each item is the cost associated with it; the maximum weight is the amount of money available.

As Gamamal pointed out, in this case you have already obtained the maximal solution. If presented with differing values for the pie/chocolate/pizza, you could use the same trick to both determine the theoretical maximum and also to simplify the units: find the GCD of all object weights, and take the floor of the maximum weight divided by this GCD to give the new unit maximum, then divide all object weights by the GCD to give the new object weights.

From this point onwards you can then apply the appropriate algorithm for the constraints you have. Wikipedia has a reasonable article on the problem and solution methods; there are also several questions with good answers on M.SE itself.