Optimize

Started working on a coding problem over at CodinGame.com yesterday. It seemed straight-forward enough until I got down to the real nitty gritty. We have a bunch of boxes that need to be loaded on a bunch of trucks. The boxes are all different sizes and weights and each truck needs to be loaded with about the same weight, so how do we go about figuring out which boxes get loaded on which trucks? My first thought was to use the same scheme you might use to add up all the numbers from one to one hundred: add the largest to the smallest. That worked fine until I found that some of the boxes are bigger than the average load for each truck, so that's going to tilt the scales a bit.

So we load each of the largest boxes onto their own truck, and adjust our average for distributing the rest of them to the remaining trucks. Continuing with my scheme, we pick off the heaviest boxes for our next truck until it would tip us over the average. Now we have four relatively simple cases, we just need to pick the one that will bring us closest to the average. We could:

1. Leave it as it, so we'll be under.
2. Add the next largest box, then we'd be over.
3. Add small boxes while we remain under the limit, or
4. Add one more small box and go over.

We could sort through all of the boxes and try and find the best combination that would bring us closest to the average, but that could take a lot of fussing, and there is no guarantee that you wouldn't end up with some combination of boxes that would be way off of our target. Besides, this is supposed to be gone quickly. If we had a quantum computer, solving this problem would be a piece of cake, but we don't, so I'm just gonna code this scheme up and see what happens.