Need Cost Minimization Algorithm for USPS Flat Rate Boxes

Question

I have a client who ships fluids in USPS flat rate boxes. If you are unfamiliar with USPS flat rate boxes, they are boxes of a certain volume that ship regardless of weight. Anything that fits in the box, ships for one low price. My client uses two box sizes: the medium flat rate boxes, and the large flat rate boxes. Additionally, my client ships their fluids in the three bottle sizes: 200ml, 375ml, and 750ml. Moreover, due to the shape of the bottles only a certain number of bottles can fit in each box, and due to their shape the cost minimization cannot be detemined by computing using the volume of each box and the bottle volumes. Thus, there are different arrangements of the bottles in each box which can work. For example, a medium box can hold 3 200ml and 2 375ml bottles or it can hold 4 200 ml bottles and 1 375ml bottle, and there are many other possible arrangements depending on the number of each size bottle. The table below, which I will call the configurations table lists the possible arrangements of each bottle in each size of box. Also, the large box costs $14.50 and the medium box costs $10.70 to ship (http://www.usps.com/prices/priority-mail-prices.htm).

SQL Table Configurations    
Box Type, 200ml, 375ml, 750ml, Cost
Medium Flat Box, 5, 0, 0, 10.70
Medium Flat Box, 4, 1, 0, 10.70
Medium Flat Box, 3, 2, 0, 10.70
Medium Flat Box, 0, 3, 0, 10.70
Medium Flat Box, 4, 0, 0, 10.70
Medium Flat Box, 3, 0, 0, 10.70
Medium Flat Box, 2, 0, 0, 10.70
Medium Flat Box, 1, 0, 0, 10.70
Medium Flat Box, 0, 2, 0, 10.70
Medium Flat Box, 0, 1, 0, 10.70
Large Flat Box, 0, 0, 2, 14.50
Large Flat Box, 0, 0, 1, 14.50
Large Flat Box, 4, 3, 0, 14.50
Large Flat Box, 0, 6, 0, 14.50
Large Flat Box, 0, 5, 0, 14.50
Large Flat Box, 0, 4, 0, 14.50
Large Flat Box, 8, 0, 0, 14.50
Large Flat Box, 7, 0, 0, 14.50
Large Flat Box, 6, 0, 0, 14.50

For example, the first row in the table says 5,0,0 and indicates that the medium box can hold 5 200 ml bottles, and no other bottles. Using the table of the arrangements above, find an algorithm for computing the optimal arrangement with respect to the shipping cost for shipping a set of x 200ml bottles, y 375 ml bottles, and z 750 ml bottles. Your algorithm should not only compute the minimal cost but it should return the optimal arrangment of bottles among the different size boxes. I would be particularly interested in seeing your algorithm expressed in SQL, but solutions in a procedural language such as Java, PHP, or C will definitely be useful also.

Answer 1

select min(Cost) 
from mytable
where 200ml<=x
and 375ml<=y
and 750ml<=z

if you want the rows back to determine the configurations you would need to add a primary key to the table to make it easier to write a subquery.