# Solving this as a integer linear programming

• 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

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