Solving this as a integer linear programming


  • 0
    U

    This is definitely an overkill, but since I've been using this method in my research recently, I hope this inspires some other fancy ideas.

    Let n = len(coins)

    Let x = [x0, x1, x2, ..., xn - 1] such that x[0] * coins[0] + x[1] * coins[1] + ... + x[n - 1] * coins[n - 1] = amount

    We can then form the integer linear programming as:

    minimize sum(x)
    subject to

    equality constraint:

    x[0] * coins[0] + x[1] * coins[1] + ... + x[n] * coins[n - 1] = amount
    

    inequality constraint:

    x[i] > 0
    x[i] is integer
    

    with the help of python optimization package cvxopt (convex optimization) and glpk (GNU Linear Programming Kit), a relatively concise piece of code can be done.

    Equality constraint are formed as matrices G and h, inequality constraint are formed as matrices A and b, c is the coefficients of objective function, in this case, is a all-one 1-d matrix

    class Solution(object):
        def coinChange(self, coins, amount):
            """
            :type coins: List[int]
            :type amount: int
            :rtype: int
            """
            if amount == 0:
                return 0
            if coins == []:
                return -1
    
            import numpy as np
            from cvxopt import matrix
            from cvxopt.glpk import ilp
    
            c = np.ones(len(coins))
            A = np.array([coins])
            b = np.array([amount])
            G = np.diag(-1 * np.ones(len(coins)))
            h = np.zeros(len(coins))
            intVars = set(range(len(coins)))
            status, isol = ilp(c = matrix(c.astype(float)),
                               G = matrix(G.astype(float)),
                               h = matrix(h.astype(float)),
                               A = matrix(A.astype(float)),
                               b = matrix(b.astype(float)),
                               I = intVars)
            return int(sum(isol)) if status == 'optimal' else -1
    

    Additionally, If return isol instead of sum(isol), you can get the exact combination of those coins

    This uses something like branch and bound method hence a optimal solution is guaranteed if exists, but it also has a O(N^K) worst case complexity, where N is the size of coins and K is the upper bound of x[i], which can be estimated by amount / min(coins), my memory can be corrupted so don't rely on my words about details

    If you really care about details or having an insomnia, here are some more dry readings

    Solving Integer Programming with Branch-and-Bound Technique
    An example in Jupyter notebook


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.