Help me design an unfair laundry machine

Question

There's a payment machine for laundry in my building which does a few frustrating things. The ones relevant to this challenge are:

• It doesn't make change. So if you pay over the amount then you are not getting that over-payment back.
• It doesn't accept coins smaller than 20c. Meaning the only coins it accepts are 20c, 50c, 1€ and 2€ (1€=100c).
• The price of running one machine is 2.30€

The third item doesn't seem immediately frustrating, however if we take a look at all the ways to make 2.30€ we can see an issue:

2€	1€	50c	20c
0	1	1	4
0	0	3	4
0	0	1	9

You may notice that in order to pay 2.30€ you must have at least a 50c coin and four 20c coins. There's no way to substitute other coins in, if you show up and you don't have that combination of coins (plus extra coins to cover the remainder) you are going to have to overpay.

I'm very suspicious that the designers of the machine set the price this way just to make it look reasonable but force over-payment. I think most people end up paying 2.50€ because it's simpler or because their pocket change doesn't meet the stringent requirements to pay exactly 2.30€

To illustrate this hypothesis I have created a strictness index. To measure it you take all the ways you can make a particular price using the available coin set and for each coin type find the option that uses the least of that coin, record the number of that coin used and sum them all up.

If we use the example above, the strictness index is 0 + 0 + 1 + 4 = 5. In fact there is no possible price with a worse strictness index for this set of coins. 5 is the limit.

Not all prices have a strictness index, for example 1.97€ can't be made with the coins above so this procedure doesn't make sense. We just ignore these values, we only care about prices that are possible to make with the given coins.

Task

In this challenge you will take a set of positive integers representing coin values and calculate the maximum strictness index a price can have in this coin system.

The input set will always contain at least 2 values, there will never be duplicates and you may assume it is in strictly ascending or descending order.

This is code-golf so the goal is to minimize the size of your source code as measured in bytes.

Test cases

2 5 10 20 -> 5
2 3 -> 3
2 3 5 -> 2
1 8 -> 7
2 4 -> 2

Answer 1

Jelly, 19 bytes

Œṗf³$ƑƇœ&/¹¡L
P!Ç€Ṁ

Try it online!

-1 thanks to Jonathan Allan.

Unlike Vyxal, Jelly's multiset intersection appears to work properly.

This is roughly \$O\left(2^{\left(\prod{s}\right)!}\right)\$. I'm pretty sure using caird's fork would save a few bytes but I can't be bothered for now.

P!Ç€Ṁ  Main link (takes a list of numbers)
P!     Factorial of product
   €   Map over 1...n
  Ç    Helper (see below)
    Ṁ  Take maximum

Œṗf³$ƑƇœ&/¹¡L  Helper link (takes argument n)
Œṗ             Integer partitions
      Ƈ        Filtered by...
    $Ƒ         Same under
  f³           Remove all but input
         /     Reduce by
       œ&      Multiset union
          ¹¡   N times
            L  Get final length

Answer 2

Python3, 551 bytes:

from itertools import*
def f(v):
 j,m=[],{}
 for I,n in enumerate(v):
  c=0
  while(c:=c+1):
   F,O=0,[]
   for j in permutations(Y:=[*(set(v)-{n})],len(Y)):
    s=c*n
    for i in j:s-=i*(s//i)
    if s>0:O+=[c];F=1
    else:O+=[0];F=0;break
   m[n]=max(O)if 0 not in O else(m[n]if n in m else 0)
   if F==0:break
 U,V=[],[i for i in m if m[i]]
 for i in range(1,len(V)+1):
  for j in combinations(V,i):
   n=sum(k*m[k]for k in j)
   if 0==any(any(0==(n-(t*(n//t)))%l and t*(n//t)for l in j)for t in {*v}-{*V}):U+=[sum(m[l]for l in j)]
 return max(U)

Try it online!

Answer 3

JavaScript (Node.js), 143 bytes

with(Math)f=(a,i=0,t)=>!t&&(g=n=>n>0?min(...a.map(m=>(m==t)+g(n-m))):n&&1/0,g(i,s=0)||a.map(v=>s+=g(i,t=v)),max(s,f(a,i+1,a.map(v=>i/=v*v)|i)))

Try it online!

I hope the answer is correct although I cannot verify it by any larger testcases due to its terrible time complexity.