Finding the minimum number of boxes to pack products

[Chao Li]

Homework Statement

This was a coding challenge, and I've already completed it. But I feel there must be a better solution to my approach at the moment. Especially maybe there's a mathematical approach.

You have 3 sizes of boxes, small, medium, large:
small: holds 3 items
medium: holds 5 items
large: holds 9 items

If some one wants N items, how many x small, y medium and z large boxes to you need to pack that exact number, while ensuring that you use the minimum number of boxes?

I've solved this using loops, but I'm just wondering if anyone have a mathematical solution for this?

Homework Equations

3x + 5y + 9z = N
solve for x, y, z such that x + y + z is a minimum

The Attempt at a Solution

int xlim = number/smallPackSize;
int ylim = number/mediumPackSize;
int zlim = number/largePackSize;

// loop thru all possibility
for (int x = 0; x <= xlim; x++) {
    for (int y = 0; y <= ylim; y++) {
        for (int z = 0; z <= zlim; z++) {
            int totalProduct = smallPackSize*x + mediumPackSize*y + largePackSize*z;

            // if total product number equals what we requested, save this combination.
            if (totalProduct == number && totalProduct != 0) {
                smallPackNo.add(x);
                mediumPackNo.add(y);
                largePackNo.add(z);

                totalPackNo.add(x + y + z);
            }
        }
    }
}

<Moderator's note: edited to add code tags. Please use them when posting code.>
Then just find the x,y,z combination that is a minimum from the lists.

This solution works. But I am concerned that it will be slow with large numbers. Does anyone have a more efficient method?

 

[stockzahn]

I think for a large number $N$ one can say use as much large sized packages as possible. So maybe it is faster to

1) calculate the number of large packages needed ($N/9 = ...$) and skip the digits after the dot
2) calculate the residual items ($N\;mod\;9 = x$), where $x$ only can be a number beyween 1 and 8 (if it is 0, the task is solve)
3) and then find rules depending on $x$ (e.g. if $x = 8$ then use on additional medium sized and one additional small sized package or if $x = 1$, then decrease the number of large sized packages by one and add two medium sized packages instead, ...)