Thuật toán giảm thiểu chi phí cho USPS Hộp giá phẳng

Question

Tôi có một khách hàng chuyên chở chất lỏng trong các hộp giá phẳng của USPS. Nếu bạn không quen thuộc với các hộp tỷ lệ căn hộ USPS, chúng là những hộp có khối lượng nhất định mà không phân biệt trọng lượng. Bất cứ thứ gì vừa vặn trong hộp, đều có giá thấp. Khách hàng của tôi sử dụng hai kích thước hộp: các hộp tỷ lệ căn hộ trung bình và các hộp tỷ lệ căn hộ lớn. Ngoài ra, khách hàng của tôi vận chuyển chất lỏng của họ trong ba kích thước chai: 200ml, 375ml và 750ml. Hơn nữa, do hình dạng của chai chỉ có một số chai nhất định có thể phù hợp trong mỗi hộp, và do hình dạng của chúng, việc giảm thiểu chi phí không thể bị hạn chế bởi tính toán bằng cách sử dụng thể tích của mỗi hộp và khối lượng chai. Vì vậy, có những sắp xếp khác nhau của các chai trong mỗi hộp có thể làm việc. Ví dụ, một hộp trung bình có thể chứa 3 chai 200ml và 2 chai 375ml hoặc có thể chứa 4 chai 200 ml và 1 chai 375ml, và có nhiều sắp xếp khác có thể tùy thuộc vào số lượng từng chai kích thước. Bảng bên dưới, mà tôi sẽ gọi cho bảng cấu hình liệt kê các sắp xếp có thể có của mỗi chai trong mỗi kích thước của hộp. Ngoài ra, hộp lớn có giá 14,50 đô la và hộp trung bình có giá 10,70 đô la để giao hàng (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 

Ví dụ: hàng đầu tiên trong bảng cho biết 5,0,0 và cho biết hộp trung bình có thể chứa 5 chai 200 ml và không có chai nào khác. Sử dụng bảng sắp xếp ở trên, tìm một thuật toán để tính toán sự sắp xếp tối ưu đối với chi phí vận chuyển để vận chuyển một bộ x 200ml chai, y 375 ml chai và z 750 ml chai. Thuật toán của bạn không chỉ tính toán chi phí tối thiểu mà còn trả lại sự sắp xếp tối ưu của các chai giữa các hộp kích thước khác nhau. Tôi sẽ đặc biệt quan tâm đến việc thấy thuật toán của bạn được thể hiện trong SQL, nhưng các giải pháp trong ngôn ngữ thủ tục như Java, PHP, hoặc C chắc chắn sẽ hữu ích.

Answer 1

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

nếu bạn muốn hàng trở lại xác định cấu hình bạn cần thêm khóa chính vào bảng để dễ dàng viết truy vấn con hơn.