# 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()
