This is something I did for a bus travel company a long time ago, and I was never happy with the results. I was thinking about that old project recently and thought I'd revisit that problem.

Problem:

Bus travel company has several buses with different passenger capacities (e.g. 15 50-passenger buses, 25 30-passenger buses ... etc). They specialized in offering transportation to very large groups (300+ passengers per group). Since each group needs to travel together they needed to manage their fleet efficiently to reduce waste.

For instance, 88 passengers are better served by three 30-passenger buses (2 empty seats) than by two 50-passenger buses (12 empty seats). Another example, 75 passengers would be better served by one 50-passenger bus and one 30-passenger bus, a mix of types.

What's a good algorithm to do this?