## Frobenius Numbers – Round Robin Algorithm

Frobenius numbers are solutions to the coin problem. Let be coin denominations; what is the smallest sum of money that cannot be obtained using these coins? More formally, define the Frobenius number as the greatest number that is not a linear combination with . The Frobenius number exists if and only if and . A special case of Frobenius numbers involves the interestingly named McNugget numbers, and there is a well-known formula when given by sometimes known as the Chicken McNugget Theorem.

In the article “The Money Changing Problem revisited: Computing the Frobenius number in time O(ka1)” (PDF link), published in 2005 by Sebastian Böcker & Zsuzsanna Lipták, a beautiful algorithm known as the round robin algorithm for finding Frobenius numbers with potentially large is described. Here is a Java implementation I wrote a a little while ago; I can no longer remember under what circumstances integer overflow would occur, but since infinity is represented as -1, the program can be easily rewritten with long or BigInteger if desired. Note that frobenius() does not enforce that the input array be sorted ascending, and also the improvements discussed on page 5 of the article are not implemented.

Another interesting approach involving circulant graphs can be found in “Faster Algorithms for Frobenius Numbers” (PDF link), published by Dale Beihoffer, et al., also in 2005.

import java.util.Arrays; public class FrobeniusNums { public static void main(String[] args) { int[] mcNug = {6, 9, 20}; System.out.println(frobenius(mcNug)); } static int frobenius(int[] nums) { int[] ns = new int[nums[0]]; Arrays.fill(ns, -1); ns[0] = 0; for (int i = 1; i < nums.length; i++) { int d = gcd(nums[0], nums[i]); for (int r = 0; r < d; r++) { int n = -1; if (r == 0) n = 0; else { int q = r; while (q < nums[0]) { if (ns[q] != -1 && (ns[q] < n || n == -1)) n = ns[q]; q += d; } } if (n != -1) for (int j = 0; j < nums[0] / d; j++) { n += nums[i]; int p = n % nums[0]; if (ns[p] != -1 && (ns[p] < n || n == -1)) n = ns[p]; ns[p] = n; } } } int max = 0; for (int i = 0; i < nums[0]; i++) if (ns[i] == -1 || ns[i] > max) max = ns[i]; if (max == -1) return -1; return max - nums[0]; } static int gcd(int a, int b) { return (b == 0) ? a : gcd(b, a % b); } }

## Leave a Reply