Optimize my wings order

Question

This tweet lists the possible orders for Wings of a Chinese restaurant¹:

When ordering Pizza I usually calculate what size gives me the best Pizza-price ratio which is a simple calculation. However minimizing the price of an order at this restaurant isn't such a simple task, so I'd like to be prepared for my next order there.

Challenge

Given an integer greater or equal to \$4\$, your task is to return one possible order which minimizes the price (overall cheapest) and the number of deals.

Example

If I were to order \$100\$ Wings, it turns out the best bargain will cost \$$111.20\$. However there are multiple orders which will cost that amount, namely:

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

Since the first order will use the least amount of deals (\$2\$) the result will be [50,50].

Rules

• Input will be some integer \$n \geq 4\$
• Output will be a list/array/... of order sizes that sum up to \$n\$ and minimize the order's price
  • you may choose to return all possible orders

Testcases

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)

Note: These testcases list all possible outputs including the price, you're only required to output one and you're not required to output the price!

---

_{1: You can find the data as a CSV here.}

Answer 1

JavaScript (ES6), 123 bytes

Returns the order as a space-separated string.

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

Try it online!

How?

Given a number \$n\$ of wings, we recursively apply the following strategy.

High values: \$n>128\$ or \$n=125\$

For high values, our best option is to buy \$125\$ wings. So that's what we're doing as long as \$n\$ is greater than or equal to \$129\$ or when \$n\$ is exactly equal to \$125\$.

We can't do that for \$125 < n < 129\$ because we'd be left with less than \$4\$ wings to buy, which is not possible.

Low values: \$n<31\$

For \$n<31\$, the best deal is to buy all remaining wings at once, except for \$n=24\$ which must be purchased as either \$2\times 12\$, \$18+6\$ or \$15+9\$. We arbitrarily buy \$9\$ wings in that case.

Range \$31 \le n \le 50\$

In this range, buying \$25\$ wings usually leads to an optimal order. But the following exceptions apply:

• If \$n\$ is a multiple of \$5\$, we must buy all remaining wings at once.
• If \$n=49\$, the best deals are \$40+9\$ and \$28+21\$. We arbitrarily buy \$9\$ wings in that case.

Range \$51 \le n \le 53\$

We can't buy \$50\$ wings in that range or we'll be left with less than \$4\$ wings. Our best option is to buy \$25\$ of them instead. (We could buy \$2\times26\$ wings for \$n=52\$, but buying \$25+27\$ is just as good.)

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

In this range, buying \$50\$ wings usually leads to an optimal order. But the following exceptions apply:

• If \$n=70\$, we must buy all of them at once.

• If \$n\$ is in \$\{80,86,89,92,98,105,108\}\$, we must buy \$80\$ wings. These values are encoded with the following bitmask, where the least significant bit is mapped to \$80\$ and the most significant one to \$108\$:

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

Answer 2

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

Try it online!

Optimized from Arnauld's answer

Differences

• 51≤n≤53 is merged into 31≤n≤50 (8 bytes save)
• Rewrite the bitmap (3 bytes save)
• Rearrange some logic (4 6 7 bytes saved)

Answer 3

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

Try it online! Link includes header that tests all values from \$ n \$ down to 1, remove it if you only want to test \$ n \$ itself. Uses @Arnauld's algorithm. Edit: Saved 5 bytes by purchasing 95 wings as 80 + 15 instead of 50 + 45. Explanation:

.+
$*

Convert to unary.

{`

Repeat until no more deals can be purchased.

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

Find a way of purchasing deals and capture and duplicate one of the deals.

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

Convert the captured deal to decimal and subtract it from \$ n \$.

Deals are purchased under the following conditions:

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

Purchase 80 wings if that leaves 0, 6, 9, 12, 15, 18, 25 or 28 wings.

1{70}$

Purchase 70 wings if that's all we need.

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

Purchase 9 wings if that leaves 15 or 40 wings.

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

Purchase 30, 35, 40 or 45 wings if that's all we need.

1{26,29}$

Purchase 26, 27, 28 or 29 wings if that's all we need.

1{4,23}$

Purchase 4 to 23 wings if that's all we need.

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

Purchase 125, 50 or 25 wings if we can and if we can still purchase more wings exactly. Note that we have these options at the end of the alternation so that the exact purchases are tested first.