Julia JuMP solver for the coin knap sack problem

coin-knapsack.jl

#  coin problem: Given an array of coin denominations,
#  write a function that returns the minimum number of
#  coins that make up a given amount N. There is always
#  a coin of value 1 in the coin denominations, so you
#  don't have to worry about amounts that cannot possibly
#  be formed. 
#  Example:
#  23, {1,7,9} should return 3 (two 7s + 9);
#  21, {1,7,9} should return 3  (three 7s);
#  15, {1,7,9} should return 3 (two 7s + 1);

using JuMP
using Cbc
m = Model(solver=CbcSolver())

denoms = [1, 7, 9, 11, 50, 128]
total = 1110003

@variable(m, x[1:length(denoms)], Int, lowerbound=0)
@constraint(m, dot(denoms, x) == total)
@objective(m, Min, sum(x))
s = @time solve(m)

n = 0
results = [(d, getvalue(x[i])) for (i, d) in enumerate(denoms)]
coins  = sum([v for (d,v) in results])


for (d,v) in results
	if (v != 0) 
		println(d, " x ", v)
	end
end
println("_ x ", coins)

coin-knapsack.py

import sys
import numpy as np
import timeit

def worker(total, coins, state, gmin, prev): 
	if sum(state) >= gmin:
		return None
	value = np.dot(state, coins)
	w = sum(state)
	if value > total:
		return None
	if value == total:
		return state
	m = gmin
	best = None
	diff = (total-value)
	# only LSV for state set can be modified
	for (i,c) in [(i,c) for (i,c) in enumerate(coins) if c <= prev]:
		min_steps = diff/c
		if min_steps + w > m:
			continue
		n = 1
		# you can do 7*9 or 9*7, always fast-track for 7 nines (and for any number of times)
		if c == prev and c != 1 and diff > c*coins[i+1]: 
			n = coins[i+1] * (diff/(c*coins[i+1])) 
		state1 = state # copy
		state1[i] += n 
		state2 = worker(total, coins, state1, m, c)
		if state2:
			# this is a solution (probably not the best)
			if sum(state2) < m:
				m = sum(state2)
				best = state2[::]
		state1[i] -= n
	return best

"""
coins contains coins like [1,7,9]
"""
def getMinCount(total, coins):
	# sort to 9, 7, 1
	coins = list(sorted(coins,reverse=True))
	state = [0]*len(coins)
    # gmin is all 1s
	try:
		best = worker(total, coins, state, total, coins[0])
	except KeyboardInterrupt:
		pass
	print total, "=", " + " . join(["%d$ x %d" % (c, best[i]) for (i,c) in enumerate(coins)])
	print sum(best), " coins"
		

def main(args):
	run10 = lambda s : (timeit.timeit(s, setup="from __main__ import getMinCount", number=1))
	ops=[
	"getMinCount(23, [1,7,9])",
	"getMinCount(21, [1,7,9])",
	"getMinCount(15, [1, 7, 9])",
	"getMinCount(111, [1, 7, 9, 11])",
	"getMinCount(1110003, [1, 7, 9, 11, 50, 128])"]
	for op in ops:
		print "%d ns\n" % (run10(op)*1e9)

if __name__ == "__main__":
	main(sys.argv[1:])