I have a client who sends liquids to USPS fixed rate boxes. If you are not familiar with USPS fixed rate boxes, these are boxes with a certain volume that are delivered regardless of weight. Everything that fits in the box comes at one low price. My client uses two box sizes: medium-sized fixed-rate scales and large fixed-rate blocks. In addition, my client sends his liquids in three bottle sizes: 200 ml, 375 ml and 750 ml. In addition, because of the shape of the bottles, only a certain number of bottles can be placed in each box, and because of their shape, cost minimization cannot be determined by calculating using the volume of each box and the volume of bottles. Thus, in each box there are various bottle devices that can work. For example, an average box may contain 3,200 ml and 2,375 ml of a bottle, or may contain 4,200 ml of a bottle and 1,375 ml of a bottle, and there are many other possible mechanisms depending on the number of bottles of each size. The table below, which I will call the configuration table, lists the possible options for each bottle in each box size. In addition, a large box costs $ 14.50, and an average box costs $ 10.70 for delivery ( 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 middle box may contain 5,200 ml of bottles and no other bottles. Using the table of the above diagrams, find an algorithm for calculating the optimal layout for delivery costs for delivering a set of 200 ml bottles, 375 ml bottles and 750 ml bottles. Your algorithm should not only calculate the minimum costs, but also should return the optimal arrangement of bottles among different boxes. I would be particularly interested in seeing your algorithm expressed in SQL, but procedural language solutions such as Java, PHP, or C would definitely be useful.