Algorithms to compute Frobenius Numbers of a set of positive integers

Question

Frobenius numbers of a set exist iff the gcd of the numbers of the set is 1. Given a set of positive integers with at most 10 elements such that the gcd of all the elements is 1, how can we compute the Frobenius number of the set?

Here is the link to the original problem: https://icpcarchive.ecs.baylor.edu/external/62/6298.pdf Sylvester's formula can be used to find the Frobenius number of a set of 2 elements.

Landscapist

Hi,it can be useful : en.m.wikipedia.org/wiki/Coin_problem – Anodize

geeksforgeeks.org/frobenius-coin-problem – Anodize

Answer 1

There are quite a few algorithms around for this, but the best option for you is probably the one in this 2004 paper by Bocker and Liptak. The pseudocode can be found on p968, though it's worth reading through the paper because it's quite a neat little algorithm.

Territory

Would you mind accepting the answer in that case? Clears it off the unanswered questions queue then :) – Territory

I wasn't aware of the 'accept' thing :P. I have accepted it now. – Landscapist