Zoptymalizuj moją kolejność skrzydeł

Ten tweet zawiera listę możliwych zamówień na Skrzydła chińskiej restauracji ¹ :

Przy zamawianiu pizzy zwykle obliczam, jaki rozmiar daje mi najlepszy stosunek ceny do pizzy, co jest prostym obliczeniem. Jednak zminimalizowanie ceny zamówienia w tej restauracji nie jest tak prostym zadaniem, dlatego chciałbym być przygotowany na następne zamówienie.

Wyzwanie

Biorąc pod uwagę liczbę całkowitą większą lub równą $4$ , Twoim zadaniem jest zwrócić jedno możliwe zamówienie, które minimalizuje cenę (ogólnie najtańszą) i liczbę ofert.

Przykład

Gdybym zamówił $100$ Skrzydeł, okazałoby się, że najlepsza okazja kosztuje $$111.20$ . Istnieje jednak wiele zamówień, które będą kosztować tę kwotę, a mianowicie:

[50,50],[25,25,50],[25,25,25,25]

Ponieważ pierwsze zamówienie wykorzysta najmniejszą liczbę ofert ( $2$ ), wynik będzie [50,50].

Zasady

Wejście będzie jakąś liczbą całkowitą $n \geq 4$
Wynikiem będzie lista / tablica / ... rozmiarów zamówień, które sumują się do $n$ i minimalizują cenę zamówienia
- możesz zwrócić wszystkie możliwe zamówienia

Przypadki testowe

4 -> [4]  (4.55)
23 -> [23]  (26.10)
24 -> [6,18],[9,15],[12,12]  (27.20)
31 -> [6,25]  (34.60)
32 -> [4,28],[6,26],[7,25]  (35.75)
33 -> [4,29],[5,28],[6,27],[7,26],[8,25]  (36.90)
34 -> [6,28],[9,25]  (38.00)
35 -> [35]  (39.15)
125 -> [125]  (139.00)
200 -> [25,50,125]  (222.40)
201 -> [26,50,125]  (223.55)
250 -> [125,125]  (278.00)
251 -> [26,50,50,125]  (279.15)
418 -> [15,28,125,125,125],[18,25,125,125,125]  (465.20)
1001 -> [26,50,50,125,125,125,125,125,125,125]  (1113.15)
12345 -> [15,80,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125],[25,70,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125],[45,50,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125]  (13728.10)

Uwaga: listy te testami wszystkich możliwych wyjść w tym cenę, jesteś zobowiązany jedynie do wyjścia jednego , a ty nie wymaga wyjścia cena!

_{1: Można znaleźć dane jako CSV tutaj .}

code-golf optimization integer-partitions ბიმო
źródło

Prawdziwe pytanie brzmi: kto zamawia 200, a nawet 100 skrzydeł? ...

Erik the Outgolfer

@Quintec: Dlaczego potrzebujesz więcej testów?

ბიმო

Dwie odpowiedzi błędnie zinterpretowały wymagania, ponieważ wystarczy jedynie zminimalizować cenę. Ponieważ minimalizowanie ceny i liczby ofert jest niejednoznaczne (najniższa cena dostępna ze sposobów o najniższej liczbie ofert lub najniższa liczba ofert dostępna ze sposobów o najniższej cenie), warto byłoby zmodyfikować wymóg, aby był bardziej precyzyjny

trichoplax

Powiązane: Co zrobić z 10 litrowym sosem Heinz BBQ? ;)

Laurel

Zauważam, że dla

cena podana jest przez

n \leq 23

$n \leq 23$

\frac{1}{20} ⌈ (\frac{68 n}{3}) ⌉

$\frac 1 {20} \lceil \left ( \frac {68 n} 3 \right ) \rceil$

25 < n <= 50

$25 < n <= 50$

25

$25$

n - 25

$n - 25$

n < 29

$n < 29$

70

$70$

80

$80$

125

$125$

Neil

Odpowiedzi:

JavaScript (ES6), 123 bajty

Zwraca kolejność jako ciąg rozdzielony spacjami.

f=n=>n?(x=n>128|n==125?125:n>50?n<54?25:n-70?302256705>>n-80&n>79&n<109?80:50:n:n-24&&n-49?n<31|n%5<1?n:25:9)+' '+f(n-x):''

Wypróbuj online!

W jaki sposób?

$n$

$n>128$ $n=125$

$125$ $n$ $129$ $n$ $125$

$125 < n < 129$ $4$

$n<31$

$n<31$ $n=24$ $2\times 12$ $18+6$ $15+9$ $9$

$31 \le n \le 50$

$25$

$n$ $5$
$n=49$ $40+9$ $28+21$ $9$

$51 \le n \le 53$

$50$ $4$ $25$ $2\times26$ $n=52$ $25+27$

$54 \le n \le 128$ $n \neq 125$

$50$ skrzydeł zazwyczaj prowadzi do optymalnego zamówienia. Obowiązują jednak następujące wyjątki:

$n=70$ , musimy kupić je wszystkie naraz.
$n$ $\{80,86,89,92,98,105,108\}$ $80$ $80$ $108$ :

$10010000001000001001001000001_{(2))} = 302256705_{(10)}$ $10010000001000001001001000001_{(2)} = 302256705_{(10)}$

Arnauld
źródło

JavaScript (Node.js) , 112 108 106 105 bajtów

f=n=>n?(x=n>128|n==125?125:n>53&n!=70?1629>>n/3+6&n<99==n%3/2?80:50:~n%25?n>30&&n%5?25:n:9)+' '+f(n-x):''

Wypróbuj online!

Zoptymalizowane na podstawie odpowiedzi Arnaulda

Różnice

51≤n≤53 jest scalane w 31≤n≤50 (8 bajtów zapisu)
Przepisz bitmapę (zapisz 3 bajty)
Zmień układ logiki ( zapisane 4 6 7 bajtów)

l4m2
źródło

Retina 0.8.2 , 160 155 bajtów

.+
$*
{`\b(1{80}(?=((111){2,6}|1{25}|1{28})?$)|1{70}$|1{9}(?=.{15}$|.{40}$)|(1{5}){6,9}$|1{26,29}$|1{4,23}$|1{125}|1{50}|1{25})+$
$1,$&
(1+),\1(1*)$
$.1,$2

Wypróbuj online! Link zawiera nagłówek, który testuje wszystkie wartości z $n$ do 1, usuń go, jeśli chcesz tylko przetestować $n$ samo. Wykorzystuje algorytm @ Arnauld. Edycja: Zapisano 5 bajtów, kupując 95 skrzydeł jako 80 + 15 zamiast 50 + 45. Objaśnienie:

.+
$*

Konwertuj na unary.

{`

Powtarzaj, aż nie będzie można kupić więcej ofert.

{`\b(1{80}(?=((111){2,6}|1{25}|1{28})?$)|1{70}$|1{9}(?=.{15}$|.{40}$)|(1{5}){6,9}$|1{26,29}$|1{4,23}$|1{125}|1{50}|1{25})+$
$1,$&

Znajdź sposób zakupu ofert, a następnie przechwyć i zduplikuj jedną z ofert.

(1+),\1(1*)$
$.1,$2

Konwertuj przechwyconą ofertę na dziesiętną i odejmij ją $n$ .

Oferty są kupowane pod następującymi warunkami:

1{80}(?=((111){2,6}|1{25}|1{28})?$)

Kup 80 skrzydeł, jeśli pozostawia 0, 6, 9, 12, 15, 18, 25 lub 28 skrzydeł.

1{70}$

Kup 70 skrzydeł, jeśli to wszystko, czego potrzebujemy.

1{9}(?=.{15}$|.{40}$)

Kup 9 skrzydeł, jeśli pozostawi to 15 lub 40 skrzydeł.

(1{5}){6,9}$

Kup 30, 35, 40 lub 45 skrzydeł, jeśli to wszystko, czego potrzebujemy.

1{26,29}$

Kup 26, 27, 28 lub 29 skrzydeł, jeśli tylko tego potrzebujemy.

1{4,23}$

Kup od 4 do 23 skrzydeł, jeśli to wszystko, czego potrzebujemy.

1{125}|1{50}|1{25}

Kup 125, 50 lub 25 skrzydeł, jeśli możemy i jeśli nadal możemy dokładnie kupić więcej skrzydeł. Pamiętaj, że mamy te opcje na końcu zmiany, więc najpierw dokładnie testowane są dokładne zakupy.

Neil
źródło