Konieczny algorytm minimalizacji kosztów dla płaskich pól USPS

Question

Mam klienta, który wysyła płyny w pudełkach o stałej stawce USPS. Jeśli nie znasz pudełek ryczałtowych USPS, są to pudełka o określonej objętości, wysyłane niezależnie od wagi. Wszystko, co mieści się w pudełku, jest dostarczane za jedną niską cenę. Mój klient używa dwóch rozmiarów pudeł: średnio płaskich pudełek i dużych pudełek o stałej stawce. Dodatkowo mój klient wysyła płyny w trzech rozmiarach butelek: 200 ml, 375 ml i 750 ml. Ponadto, ze względu na kształt butelek, tylko pewna liczba butelek może zmieścić się w każdym pudełku, a ze względu na ich kształt minimalizacja kosztów nie może być określona przez obliczenia z wykorzystaniem objętości każdego pudełka i objętości butelek. Tak więc, istnieją różne układy butelek w każdym pudełku, które mogą działać. Na przykład, średni pojemnik może pomieścić 3 200 ml i 2 375 ml butelek lub może pomieścić 4 butelki 200 ml i 1 375 ml butelkę, a istnieje wiele innych możliwych ustawień w zależności od liczby butelek o każdym rozmiarze. Poniższa tabela, którą nazwałbym tabelą konfiguracje, zawiera listę możliwych aranżacji każdej butelki w każdym rozmiarze pudełka. Również duże pudełko kosztuje 14,50 $, a średnie pudełko kosztuje 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 

Na przykład, pierwszy wiersz w tabeli mówi 5,0,0 i wskazuje, że podłoże może zawierać pole 5 200 ml butelek i żadnych innych butelek. Korzystając z tabeli powyższych rozwiązań, znajdź algorytm obliczania optymalnego układu w odniesieniu do kosztów wysyłki do wysyłki zestawu butelek x 200 ml, butelek 375 ml i butelek 750 ml. Twój algorytm powinien nie tylko obliczyć minimalny koszt, ale powinien również zwrócić optymalną aranżację butelek między różnymi polami rozmiarów. Byłbym szczególnie zainteresowany zobaczeniem twojego algorytmu wyrażonego w SQL, ale rozwiązania w języku proceduralnym, takim jak Java, PHP lub C z pewnością również będą użyteczne.

Answer 1

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

jeśli chcesz, aby wiersze z powrotem określały konfiguracje potrzebne do dodania klucza podstawowego do tabeli, aby ułatwić pisanie podkwerendy.