Minimum number of trips for a truck with weight limit of $200$ to transport boxes with weights 81, 73, 67, 49, 37, 34, 30, and 26

elementary-number-theorypacking-problempuzzle

My 9-year-old son had the following math problem to solve:

A truck can carry $200$kg or less. We have 8 different boxes with given
weights:

$81$kg, $73$kg, $67$kg, $49$kg, $37$kg, $34$kg, $30$kg, and $26$kg

What is the minimum number of trip required to move all boxes from
city A to city B.

I looked at it for 5 minutes and couldn't figure out a meaningful approach other than brute force.

I was in front of my computer and quickly wrote a MATLAB script to bruteforce it.

The solution was 2 trips: one with boxes $81$, $49$, and $67$; and the other with boxes $73$, $37$, $30$, $26$, and $34$.

Is there an obvious way, or at least one more clever than brute force, to solve that kind of problem?

Here, it's not that hard because we only have 8 boxes. But what about a similar problem with a bigger set? Can we only rely on brute force?

Bonus question:

What is this supposed to teach to a 9yo kid ?

Best Answer

Perhaps the main lesson would be:

The greedy approach is not always optimal

What would be the greedy method? Pack the truck with heaviest boxes first until you cannot add any more boxes. This results in a first tour with 81+73+37=191 and a second tour with 67+49+34+30=180 and then a final tour with the one remaining 26 kg. The fact that the 26 kg just barely fail to fit into the second tour are perhaps intended to annoy you and make you play around to somehow achieve two tours.

  • Replacing the 37 of tour with something smaller? There is no way to get four boxes with 81+73 as already 26+30 is too much.
  • Replace the 73 with something smaller? doing so and continuing greedily, we arrive at 81+67+49=197 and the rest on the second tour - and done!

Given the age, however, I suppose this problem would be more appropriate if the trial-and-error phase could be performed physically (e.g., moving around suitable paper cutouts). But the numbers used in this problem do not seem to allow that easily.

Related Question