Optimizar mi orden de alas

Este tweet enumera los posibles pedidos de Wings of a Chinese restaurant ¹ :

Cuando ordeno pizza, generalmente calculo qué tamaño me da la mejor relación precio pizza, que es un cálculo simple. Sin embargo, minimizar el precio de un pedido en este restaurante no es una tarea tan simple, por lo que me gustaría estar preparado para mi próximo pedido allí.

Desafío

Dado un número entero mayor o igual a , su tarea es devolver un posible pedido que minimice el precio (en general más barato) y el número de ofertas. $4$

Ejemplo

Si tuviera que pedir alas, resulta que la mejor oferta costará . Sin embargo, hay varios pedidos que costarán esa cantidad, a saber: $100$ $$111.20$

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

Dado que el primer pedido usará la menor cantidad de ofertas ( $2$ ), el resultado será [50,50].

Reglas

La entrada será un número entero $n \geq 4$
La salida será una lista / matriz / ... de tamaños de pedido que suman $n$ y minimizan el precio del pedido
- puedes elegir devolver todos los pedidos posibles

Casos de prueba

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)

Nota: ¡ Estos casos de prueba enumeran todas las salidas posibles, incluido el precio, solo se requiere que produzca una y no se requiere que envíe el precio!

_{1: Puede encontrar los datos como CSV aquí .}

code-golf optimization integer-partitions ბიმო
fuente

La verdadera pregunta es, ¿quién ordena 200 o incluso 100 alas? ...

Erik the Outgolfer

@Quintec: ¿Por qué, necesitas más casos de prueba?

ბიმო

Dos respuestas han malinterpretado los requisitos, ya que solo necesitan minimizar el precio. Dado que minimizar el precio y el número de ofertas es ambiguo (el precio más bajo disponible de las formas con el número más bajo de ofertas, o el número más bajo de ofertas disponibles de las formas con el precio más bajo) valdría la pena editar el requisito para ser más explícito

trichoplax

Relacionado: ¿Qué hacer con 10 litros de salsa BBQ Heinz? ;)

Laurel

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$

Respuestas:

JavaScript (ES6), 123 bytes

Devuelve el pedido como una cadena separada por espacios.

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):''

Pruébalo en línea!

¿Cómo?

$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$

$n=70$
$n$ $\{80,86,89,92,98,105,108\}$ $80$ $80$ $108$

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

Arnauld
fuente

JavaScript (Node.js) , 112 108 106 105 bytes

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):''

Pruébalo en línea!

Optimizado de la respuesta de Arnauld

Las diferencias

51≤n≤53 se fusiona en 31≤n≤50 (8 bytes guardados)
Reescribe el mapa de bits (3 bytes guardados)
Reorganizar algo de lógica ( 4 6 7 bytes guardados)

l4m2
fuente

Retina 0.8.2 , 160 155 bytes

.+
$*
{`\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

$n$ $n$

.+
$*

Convierte a unario.

{`

Repita hasta que no se puedan comprar más ofertas.

{`\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,$&

Encuentre una forma de comprar ofertas y capture y duplique una de las ofertas.

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

$n$

Las ofertas se compran bajo las siguientes condiciones:

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

Compra 80 alas si eso deja 0, 6, 9, 12, 15, 18, 25 o 28 alas.

1{70}$

Compra 70 alas si eso es todo lo que necesitamos.

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

Compra 9 alas si eso deja 15 o 40 alas.

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

Compra 30, 35, 40 o 45 alas si eso es todo lo que necesitamos.

1{26,29}$

Compra 26, 27, 28 o 29 alas si eso es todo lo que necesitamos.

1{4,23}$

Compra de 4 a 23 alas si eso es todo lo que necesitamos.

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

Compre 125, 50 o 25 alas si podemos y si todavía podemos comprar más alas exactamente. Tenga en cuenta que tenemos estas opciones al final de la alternancia para que las compras exactas se prueben primero.

Neil
fuente