Optimiser ma commande d'ailes

17

Ce tweet répertorie les commandes possibles pour les ailes d'un restaurant chinois 1 :

Menu des ailes

Lors de la commande de pizza, je calcule généralement quelle taille me donne le meilleur rapport pizza-prix qui est un calcul simple. Cependant, minimiser le prix d'une commande dans ce restaurant n'est pas une tâche aussi simple, alors j'aimerais être prêt pour ma prochaine commande là-bas.

Défi

Étant donné un nombre entier supérieur ou égal à 4 , votre tâche consiste à retourner une commande possible qui minimise le prix (globalement le moins cher) et le nombre d'offres.

Exemple

Si je devais commander 100 Wings, il s'avère que la meilleure affaire coûtera 111,20 $111.20 . Cependant, plusieurs commandes coûteront ce montant, à savoir:

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

Étant donné que la première commande utilisera le moins d'offres ( 2 ), le résultat sera [50,50].

Règles

  • L'entrée sera un entier n4
  • La sortie sera une liste / tableau / ... des tailles de commande qui résument jusqu'à n et minimisent le prix de la commande
    • vous pouvez choisir de retourner toutes les commandes possibles

Cas de test

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)

Remarque: Ces tests répertorient toutes les sorties possibles, y compris le prix, vous n'êtes obligé d'en sortir qu'une et vous n'êtes pas obligé de sortir le prix!


1: Vous pouvez trouver les données au format CSV ici .

ბიმო
la source
3
La vraie question est, qui commande 200 ou même 100 ailes? ...
Erik the Outgolfer
2
@Quintec: Pourquoi avez-vous besoin de plus de tests?
ბიმო
1
Deux réponses ont mal interprété les exigences, car elles n'avaient besoin que de minimiser le prix. Étant donné que la minimisation du prix et du nombre d'offres est ambiguë (prix le plus bas disponible à partir des chemins avec le plus petit nombre d'offres, ou nombre le plus bas d'offres disponibles à partir des chemins avec le prix le plus bas), il serait utile de modifier l'exigence pour être plus explicite
trichoplax
1
Je remarque que pour le prix est donné par 1n23120(68n3)25<n<=5025n-25n<297080125

Réponses:

7

JavaScript (ES6), 123 octets

Renvoie l'ordre sous forme de chaîne séparée par des espaces.

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

Essayez-le en ligne!

Comment?

n

n>128n=125

125n129n125

125<n<1294

n<31

n<31n=242×1218+615+99

31n50

25

  • n5
  • n=4940+928+219

51n53

504252×26n=5225+27

54n128n125

50

  • n=70
  • n{80,86,89,92,98,105,108}8080108

    10010000001000001001001000001(2)=302256705(dix)

Arnauld
la source
4

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

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

Essayez-le en ligne!

Optimisé à partir de la réponse d'Arnauld

Différences

  • 51≤n≤53 est fusionné en 31≤n≤50 (sauvegarde de 8 octets)
  • Réécrire le bitmap (sauvegarde de 3 octets)
  • Réorganiser une logique ( 4 6 7 octets enregistrés)
l4m2
la source
2

0.8.2 Retina , 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

nn lui-même. Utilise l'algorithme de @ Arnauld. Edit: économisé 5 octets en achetant 95 ailes en 80 + 15 au lieu de 50 + 45. Explication:

.+
$*

Convertissez en unaire.

{`

Répétez jusqu'à ce qu'aucune autre offre ne puisse être achetée.

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

Trouvez un moyen d'acheter des offres et capturez et dupliquez l'une des offres.

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

n .

Les offres sont achetées dans les conditions suivantes:

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

Achetez 80 ailes si cela laisse 0, 6, 9, 12, 15, 18, 25 ou 28 ailes.

1{70}$

Achetez 70 ailes si c'est tout ce dont nous avons besoin.

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

Achetez 9 ailes si cela laisse 15 ou 40 ailes.

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

Achetez 30, 35, 40 ou 45 ailes si c'est tout ce dont nous avons besoin.

1{26,29}$

Achetez 26, 27, 28 ou 29 ailes si c'est tout ce dont nous avons besoin.

1{4,23}$

Achetez 4 à 23 ailes si c'est tout ce dont nous avons besoin.

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

Achetez 125, 50 ou 25 ailes si nous le pouvons et si nous pouvons toujours acheter plus d'ailes exactement. Notez que nous avons ces options à la fin de l'alternance afin que les achats exacts soient testés en premier.

Neil
la source