Solving Math Problem with Crates: A Maximum Dividers Challenge

[bamia]

Hello everyone,

I hope I'm not intruding with too simple of a request for help.

I have this math problem:

A rack space with 100 slots for plastic crates. I have two type of crates, one with 20 dividers weighing 5 grams and one with 60 dividers weighing 25 grams. I want to add crates to achieve the largest number of dividers while not exceeding 1000 grams.

so here I go:
n= # of 20 divider crate weighing 5 grams
m= # of 60 divider crate weighing 25 grams
w <= 1000 grams (Weight can't exceed 1000 grams)
n+m = 100 (total number of crates)
m=100-n
5n+25m=w (weight of the crate dividers)
5n+2500-25n=w
2500-20n=w
And then I'm stuck.

I can work out the solution by writing code to fill the rack with the 20 divider crates with a total of 500 grams and then replace one crate at time with a 60 divider one while testing for max total weight and total number of dividers and I get a result of 75n and 25m for a total dividers of 3000 weighing 1000 grams.
I can prove the same logic to work by changing the numbers a bit; for example with the second crate weighing 25 grams but having only 10 dividers instead of 60 I get 100n and 0m with a total weight of 500 grams.

Now are there equations to do this?

Thanks a lot

MOD EDIT: added some commentary in blue and moved from a technical forum, hence no template.

 

[Charles Link]

You need one more equation: $N=20n+60m$. Suggestion: Try graphing all of your equations on a graph of $m$ vs. $n$, and take the equation for $N$ for fixed $N$ and find the best selection on the graph by varying $N$.

 

[Merlin3189]

Following your analysis, when you get to 2500-20n=w then you can remember the earlier line w <= 1000
to give you 2500 - 20n <= 1000 or 1500 <= 20n so 75 <= n

The other constraint that you haven't used yet, is maximising the number of divisions.
You can write a formula for that, but since it's fairly obvious you want the maximum number of 60 boxes, then you want minimum 20 boxes , ie minimum n.
Then the smallest n greater than or equal to 75, is 75 itself.

 

[Charles Link]

The graphs of $m \leq -n+100$, along with $m \leq -n/5+40$, and $m=-n/3 +N/60$, as mentioned in post 2, show the solution very readily, but some algebra, (solving the first two equations to find where the two lines intersect), gets the very same answer. The graphic solution, IMO, shows how $N$ is maximized, subject to the two initial constraints, most clearly.

 

[bamia]

Merry Christmas and happy new year.

So I got back to working on this and graphed the three equations which work for the numbers in the first post but if I change the specifications then the equations fail.

n= # of 20 divider crate weighing 5 grams
m= # of 10 divider crate weighing 25 grams [That got changed to fewer dividers]
w <= 1000 grams (Weight can't exceed 1000 grams)

x<=100-y
x<=-y/5+40
x=-2y+N/10

The three graphs intersect at m=25,n=75,N=1750 which is not optimal use of the rack. m=0,n=100,N=2000 is optimal.

This is not home work, it was last Christmas puzzle that I read and liked to solve but unfortunately got too busy and left it all this time.

So my objective is to find an algorithm that works for all cases, obviously. As I mentioned in the first post I can do this very easily in code, in a loop, testing for different conditions to get the best result.
But I would like to know if this could be done mathematically and how. Which math should I be re-learning to solve the three equations.
Thanks

 

[Charles Link]

In this linear programming, you always need to check the endpoints at the limits of the graphs. I'm pretty sure that's what is happening here, without studying it in great detail.