USPS统一费率箱需要成本最小化算法

Question

我有一个客户在USPS统一费率箱中运输液体.如果您不熟悉USPS统一费率箱,则无论重量如何,它们都是一定量的箱子.任何适合盒子的东西都是以低价运送的.我的客户使用两种盒子大小:中等统一费率盒子和大型统一费率盒子.此外,我的客户将他们的液体装在三种瓶子中:200ml,375ml和750ml.此外,由于瓶子的形状,每个箱子中只能容纳一定数量的瓶子,并且由于它们的形状,不能通过使用每个箱子的体积和瓶子体积来计算成本最小化.因此,每个盒子中的瓶子有不同的布置,可以工作.例如,一个中型盒子可容纳3个200ml和2个375ml瓶子,或者它可容纳4个200毫升瓶子和1个375毫升瓶子,根据每个尺寸瓶子的数量,还有许多其他可能的安排.下表,我将称之为配置表列出了每种尺寸盒子中每个瓶子的可能排列.此外,大箱售价14.50美元,中型箱售价10.70美元(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

例如,表格中的第一行表示5,0,0,表示中型箱可容纳5个200毫升的瓶子,而不是其他瓶子.使用上述布置的表格,找到用于计算关于运输一组x 200ml瓶子,375ml瓶子和z 750ml瓶子的运输成本的最佳布置的算法.您的算法不仅要计算最低成本,还应该在不同大小的盒子中返回最佳的瓶子布局.我会特别感兴趣的是看到你的算法用SQL表示,但是用Java,PHP或C等过程语言的解决方案肯定也会有用.

Answer 1

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

如果您希望返回行来确定配置，则需要向表中添加主键，以便更轻松地编写子查询。