[Question]
  [
# Background
The official currency of the imaginary nation of Golfenistan is the *foo*, and there are only three kinds of coins in circulation: 3 foos, 7 foos and 8 foos.
One can see that it's not possible to pay certain amounts, like 4 foos, using these coins.
Nevertheless, all large enough amounts can be formed.
Your job is to find the largest amount that can't be formed with the coins (5 foos in this case), which is known as the [coin problem](https://en.wikipedia.org/wiki/Coin_problem).
# Input
Your input is a list `L = [n1, n2, ..., nk]` of positive integers, representing the values of coins in circulation.
Two things are guaranteed about it:
* The GCD of the elements of `L` is 1.
* `L` does not contain the number 1.
It may be unsorted and/or contain duplicates (think special edition coins).
# Output
Since the GCD of `L` is 1, every large enough integer `m` can be expressed as a non-negative linear combination of its elements; in other words, we have
```
 m = a1*n1 + a2*n2 + ... + ak*nk 
```
for some integers `ai ≥ 0`.
Your output is the largest integer that *cannot* be expressed in this form.
As a hint, it is known that the output is always less than `(n1 - 1)*(nk - 1)`, if `n1` and `nk` are the maximal and minimal elements of `L` ([reference](http://www.cis.upenn.edu/~cis511/Frobenius-number.pdf)).
# Rules
You can write a full program or a function.
The lowest byte count wins, and standard loopholes are disallowed.
If your language has a built-in operation for this, you may not use it.
There are no requirements for time or memory efficiency, except that you should be able to evaluate the test cases before posting your answer.
After I posted this challenge, user @vihan pointed out that Stack Overflow has an [exact duplicate](https://stackoverflow.com/questions/3465392/code-golf-frobenius-number).
Based on [this Meta discussion](http://meta.codegolf.stackexchange.com/questions/6896/duplicates-on-other-se-sites), this challenge will not be deleted as a duplicate; however, I ask that all answers based on those of the SO version should cite the originals, be given the Community Wiki status, and be deleted if the original author wishes to post their answer here.
# Test Cases
```
[3, 7, 8] -> 5
[25, 10, 16] -> 79
[11, 12, 13, 14, 13, 14] -> 43
[101, 10] -> 899
[101, 10, 899] -> 889
[101, 10, 11] -> 89
[30, 105, 70, 42] -> 383
[2, 51, 6] -> 49
```
  
[Answer]
# Perl, ~~60~~ ~~54~~ 51 bytes
50 bytes code + 1 bytes command line
```
$.*=$_,$r.=1x$_."|"}{$_=$.while(1x$.--)=~/^($r)+$/
```
The basic approach is to let the regex engine do the hard work with string matching. For example, it will construct a regex similar to `^(.{3})*(.{7})*(.{8})*$` and match against a string of length `n` where `n` descends from the product of the inputs until it fails to match.
Note that this will become exponentially slow as the number of arguments increases.
Usage:
Arguments are read in from STDIN (new line separated), for example:
```
printf "101\n10" | perl -p entry.pl
```
[Answer]
# Pyth, 23 bytes
```
ef!fqTs.b*NYQY^UTlQS*FQ
```
It's very slow, as it checks all values up to the product of all the coins. Here's a version that is almost identical, but 1) reduces the set of coins to those not divisible by each other and 2) only checks values up to `(max(coins) - 1) * (min(coins) - 1)` (47 bytes):
```
=Qu?.A<LiHdG+GHGQYef!fqTs.b*NYQY^UTlQS*thSQteSQ
```
## Explanation
```
                   S            range 1 to
                    *FQ         product of input
 f                             filter by
               UT                range 0 to T 
              ^  lQ              cartesian power by number of coins
   f                            filter by
      s.b*NYQY                   sum of coin values * amounts
    qT                           equals desired number T
  !                             nothing matching that filter
e                             take last (highest) element
```
[Answer]
# [R](https://www.r-project.org/), 84 78 72 bytes
For an arbitrary entry of coprimes, \$a\_1, a\_2,\ldots\$, [Frobenius' amount](https://en.wikipedia.org/wiki/Coin_problem) is given by
```
a=scan();max((1:(b<-min(a)*max(a)))[-colSums(combn(outer(a,0:b),sum(!!a)))])
```
[Try it online!](https://tio.run/##FcpBCoAgEAXQq@TuTxhomyDqFC2jhUqC0ChUA93ecPt4d41rjZLDm0qGI3YfYGf4ZeDUoG/iiGgfQrk24QehsM8o8p43nDazJ/0IQ6nWDqoRAXbSnTUjUf0B "R – Try It Online")
since it is always smaller than the product of the extreme \$a\_i\$'s. It is then a matter of combining all possible combinations (and more) within that range. Thanks to Cole Beck for suggesting `outer` with no "\*" and `colSums` rather than `apply(...,2,sum)'.
A faster but longer (by two bytes) version only considers `max(a)`:
```
a=scan();max((1:(min(a)*(b<-max(a))))[-colSums(combn(outer(a,0:b),sum(!!a)))])
```
A slightly shorter version (72 bytes) that most often takes too log or too much space to run on [Try it online](https://tio.run/##FctBCsIwEAXQu3T1fxmh050FTxKyGEOjQpOUmkA9fdT14x093npsOdRXyTAmOwFdYE79aG72pLvYvm8fhJLuGaXV9YDJtPxVhnGgbGt@1OdvU2Z5t0TPHhGgV9FJyf4F) is
```
a=scan();max((1:(b<-prod(a)))[-colSums(combn(outer(a,0:b),sum(!!a)))])
```
[Answer]
# Python2, 188 187 bytes
```
def g(L):
 M=max(L);i=r=0;s=[0]*M;l=[1]+s[1:]
 while 1:
    if any(all((l+l)[o:o+min(L)])for o in range(M)):return~-s[r]*M+r
    if any(l[(i-a)%M]for a in L):l[i]=1
    else:r=i
    s[i]+=1;i=(i+1)%M
```
The second indentation is rendered as 4 spaces on SO, those should be tabs.
Actually a 'fast' solution, not bruteforce, uses 'Wilf's Method' as described [here](http://www.math.univ-montp2.fr/%7Eramirez/Tenerif1.pdf).
[Answer]
# Javascript ES6, ~~120~~ ~~130~~ ~~126~~ ~~128~~ ~~127~~ 125 chars
```
f=a=>`${r=[1|a.sort((a,b)=>a-b)]}`.repeat(a[0]*a[a.length-1]).replace(/./g,(x,q)=>r[q]|a.map(x=>r[q+x]|=r[q])).lastIndexOf(0)
```
Alternative 126 chars version:
```
f=a=>{r=[1];a.sort((a,b)=>a-b);for(q=0;q<a[0]*a[a.length-1];++q)r[q]?a.map(x=>r[q+x]=1):r[q]=0;return r.join``.lastIndexOf(0)}
```
Test:
```
"[3, 7, 8] -> 5\n\
[25, 10, 16] -> 79\n\
[11, 12, 13, 14, 13, 14] -> 43\n\
[101, 10] -> 899\n\
[101, 10, 899] -> 889\n\
[101, 10, 11] -> 89\n\
[30, 105, 70, 42] -> 383\n\
[2, 51, 6] -> 49".replace(/(\[.*?\]) -> (\d+)/g, function (m, t, r) {
  return f(JSON.parse(t)) == r
})
```
[Answer]
# [Ruby](https://ruby-doc.org/), 108 bytes
```
->a{b=[0];m=a.min
(1..1.0/0).map{|n|c=p
a.map{|x|c|=(b!=b-[n-x])}
c&& b<<=n
return n-m if b[-m]&&b[-m]>n-m}}
```
[Try it online!](https://tio.run/##dc/daoMwFADg@zzFGQNpwWSJP1Vp44uEXBhpwYtk4ia0VJ/dnVi2EdcFQv6@c3LOMJrbchnezdl144dcaN3cjVRcH61smO0c2QnGBONvfM9s098nN7WyJ83jcJ3aSe7MizRUOXrV@5m0UQTmdJKODOfPcXDgqIXuAkZRq6NoXWq8m@elh5@flUpjKGIotYbNeJU15CSwSR6D4DgPG@5tUYVYCIQJTvxBZN8rBnqcpRvMvebPqyir6qmO/UsQsuryPy1EmP@RO8Spdxz7LHCTJb8BHqflpmxsL8fkhz91rz1Wyxc "Ruby – Try It Online")
# Explanation
```
->a{                                         input list
    b=[0];                                      list of representable integers
        m=a.min                                     minimum input
    (1..1.0/0).map{|n|                       n in range 1..
        c=p                                    c = false
          a.map{|x|c|=(b!=b-[n-x])}              check if n goes in b
            c&& b<<=n                                   put n in b
              return n-m if b[-m]&&b[-m]>n-m}}            return if m values in a row
```
]