# Code from Chapter 10 of Machine Learning: An Algorithmic Perspective (2nd Edition)
# by Stephen Marsland (http://stephenmonika.net)

# You are free to use, change, or redistribute the code in any way you wish for
# non-commercial purposes, but please maintain the name of the original author.
# This code comes with no warranty of any kind.

# Stephen Marsland, 2008, 2014

# An exhaustive search to solve the Knapsack problem
import numpy as np

def exhaustive():
    maxSize = 500    
    sizes = np.array([109.60,125.48,52.16,195.55,58.67,61.87,92.95,93.14,155.05,110.89,13.34,132.49,194.03,121.29,179.33,139.02,198.78,192.57,81.66,128.90])

    best = 0

    twos = np.arange(-len(sizes),0,1)
    twos = 2.0**twos
    
    for i in range(2**len(sizes)-1):
        string = np.remainder(np.floor(i*twos),2) 
        fitness = np.sum(string*sizes)
        if fitness > best and fitness<500:
            best = fitness
            bestString = string
    print best
    print bestString
          
exhaustive()