So as you may or may not have known, I was recently let go without cause from work and have been brushing up on various computer science algorithms to possibly help with my job search. The two problems presented below are known as the Travelling Saleswoman problem and the Knapsack problem.

The first one basically asks the question, if you had multiple points that you had to travel to around a city, what would be the shortest path to and from each of those points (assuming you only had to visit them once). The answer to this also depends where your starting point is of course. The slow way of solving it involves calculating all of the combinatorial paths (factorial tries) and finding the shortest length.

The second problem involves attempting to fit a set of different sized boxes (filled with different amounts of money in each box) in a knapsack that can only hold a certain amount of mass. The goal is to try and maximize the amount of boxes and money that you can fit in the knapsack which again involves trying a series of combinations for each box to fit. The problem also gets harder if you allow multiple boxes of the same type to fit inside the knapsack as it expands the number of attempts needed to try and find the best fit.

Anyway, here’s some code below (no comments or guarantee of code correctness) which helped me study these concepts in practice:

the_travelling_saleswoman_with_a_knapsack_problem.py

#!/usr/bin/python

import math
import os
import sys

def d(a, b):
	return math.sqrt(math.pow(b[0] - a[0], 2) + math.pow(b[1] - a[1], 2))

def brute_force(left, ban=[]):
	flag = False
	flist = []
	for i in left:
		if (i in ban):
			continue
		flag = True
		ban.append(i)
		ulist = brute_force(left, ban)
		for uitem in ulist:
			flist.append(uitem)
		ban.remove(i)
	if (len(flist) > 0):
		return flist
	if (flag == False):
		return [ban[:]]
	return []

def travelling_saleswman(items):
	leng = len(items)
	indx = range(0, leng)
	uniq = brute_force(indx)
	minl = []; mind = 0
	for i in uniq:
		path = []; dist = 0
		x = 0
		while ((x + 1) < leng):
			path.append(items[i[x]])
			dist += d(items[i[x]], items[i[x+1]])
			x += 1
		path.append(items[i[x]])
		dist = math.ceil(dist)
		#print("Path",path,dist)
		if ((mind < 1) or (dist < mind)):
			minl = path[:]; mind = dist
	print("BF-Min",minl,mind)

def nearest_item(items):
	leng = len(items)
	minl = []; minm = 0
	for i in range(0, leng):
		temp = items[:]
		start = [temp.pop(i)]; minp = 0
		while (len(temp) > 0):
			mini = 0; mind = 0
			j = (len(start) - 1)
			x = 0; l = len(temp)
			while (x < l):
				dist = d(start[j], temp[x])
				if ((mind < 1) or (dist < mind)):
					mini = x; mind = dist
				x += 1
			start.append(temp.pop(mini))
			minp += mind
		minp = math.ceil(minp)
		if ((minm < 1) or (minp < minm)):
			minl = start[:]; minm = minp
		#print("Path",start,minp)
	print("NN-Min",minl,minm)

def knapsack_one(pkgs):
	leng = len(pkgs)
	indx = range(0, leng)
	uniq = brute_force(indx)
	maxl = []; maxs = 0; maxm = 0
	for item in uniq:
		size = 0; money = 0
		temp = []
		for i in item:
			if ((pkgs[i][0] + size) > 15):
				break
			temp.append(pkgs[i]); size += pkgs[i][0]; money += pkgs[i][1]
		#print("Pkgs",temp,"%dk / $%d"%(size,money))
		if ((maxm < 1) or (money > maxm) or ((money == maxm) and (size > maxs))):
			maxl = temp[:]; maxs = size; maxm = money
	print("KS-One",maxl,"%dk / $%d"%(maxs,maxm))

def knapsack_many(pkgs):
	leng = len(pkgs)
	indx = range(0, leng)
	uniq = brute_force(indx)
	maxl = []; maxs = 0; maxm = 0
	for item in uniq:
		size = 0; money = 0
		temp = []
		for i in item:
			if ((pkgs[i][0] + size) > 15):
				break
			temp.append(pkgs[i]); size += pkgs[i][0]; money += pkgs[i][1]
		#print("PKGS-One",temp,"%dk / $%d"%(size,money))
		tlist = temp[:]; tsize = size; tmoney = money
		# attempt to add in as many larger packages as possible (highest mass first)
		z = (leng - 1); x = 0
		while (z >= (leng / 2)):
			temp = tlist[:]; size = tsize; money = tmoney
			y = z
			while (y > -1):
				if ((pkgs[y][0] + size) > 15):
					y -= 1
					continue
				temp.append(pkgs[y]); size += pkgs[y][0]; money += pkgs[y][1]
			z -= 1
			# attempt to squeeze in as many smaller packages as possible (lowest mass first)
			slist = temp[:]; ssize = size; smoney = money
			y = 0
			while (y <= (leng / 2)):
				temp = slist[:]; size = ssize; money = smoney
				i = (len(temp) - 1)
				while (i >= (len(temp) / 2)):
					#print("PKGS-Many",temp,"%dk / $%d"%(size,money))
					if ((maxm < 1) or (money > maxm) or ((money == maxm) and (size > maxs))):
						maxl = temp[:]; maxs = size; maxm = money
					size -= temp[i][0]; money -= temp[i][1]
					temp[i] = pkgs[y]; size += pkgs[y][0]; money += pkgs[y][1]
					while ((pkgs[y][0] + size) <= 15):
						temp.append(pkgs[y]); size += pkgs[y][0]; money += pkgs[y][1]
					i -= 1
				y += 1
	print("KS-Many",maxl,"%dk / $%d"%(maxs,maxm))

def main():
	cities = [[0, 60], [15, 30], [20, 65], [35, 25], [45, 15], [60, 55], [95, 80]]
	travelling_saleswman(cities)
	nearest_item(cities)
	# [1kg, $1], etc... (methods assume the list items are sorted by mass!)
	pkglist = [[1, 1], [1, 2], [2, 2], [4, 10], [12, 4]]
	knapsack_one(pkglist)
	knapsack_many(pkglist)

if (__name__ == "__main__"):
	main()

('BF-Min', [[45, 15], [35, 25], [15, 30], [0, 60], [20, 65], [60, 55], [95, 80]], 174.0)
('NN-Min', [[45, 15], [35, 25], [15, 30], [0, 60], [20, 65], [60, 55], [95, 80]], 174.0)
('KS-One', [[1, 1], [1, 2], [2, 2], [4, 10]], '8k / $15')
('KS-Many', [[1, 2], [4, 10], [4, 10], [4, 10], [1, 2], [1, 2]], '15k / $36')