Knapsack - Recurssive

knapsack.py

import numpy as np

""" 
This is NOT the polynomial time solution (should build lookup table instead).
"""


def knapsack(c, w, remaining_capacity, i=None):
    """
    Recursively solve the knapsack problem to maximize utility given the remaining capacity and items with weight w
    and utility c.
    :param c: vector a numpy vector of utilities
    :param w: vector a numpy vector of weights (> 0)
    :param remaining_capacity: numeric the remaining capacity in the knapsack
    :param i: none or integer used to track position in recursion
    :return: (utility, x) where x is a vector of items to include
    """
    if i is None:
        i = np.size(c) - 1

    if i < 0:
        return 0, np.zeros(c.shape)

    if remaining_capacity <= 0:
        return 0, np.zeros(c.shape)

    cur_weight = w[i]

    # too heavy?
    if cur_weight > remaining_capacity:
        return knapsack(c, w, remaining_capacity, i - 1)

    # calculate utility and item list WITH item
    (utility_with_item, x_with_item) = knapsack(c, w, remaining_capacity - cur_weight, i - 1)
    utility_with_item += c[i]

    # calculate utility and item list WITH item
    (utility_without_item, x_without_item) = knapsack(c, w, remaining_capacity, i - 1)

    if utility_with_item > utility_without_item:
        x_with_item[i] = 1
        return utility_with_item, x_with_item

    return utility_without_item, x_without_item

items = ['map', 'compass', 'water', 'sandwich', 'glucose', 'tin', 'banana', 'apple', 'cheese', 'beer', 'suntan cream',
         'camera', 'T-shirt', 'trousers', 'umbrella', 'waterproof trousers', 'waterproof overclothes', 'note-case',
         'sunglasses', 'towel', 'socks', 'book']
utilities = np.array([150, 35, 200, 160, 60, 45, 60, 40, 30, 10, 70, 30, 15, 10, 40, 70, 75, 80, 20, 12, 50, 10])
weights = np.array([9, 13, 153, 50, 15, 68, 27, 39, 23, 52, 11, 32, 24, 48, 73, 42, 43, 22, 7, 18, 4, 30])

# solve
max_utility, item_indices = knapsack(utilities, weights, 400)

print "Max utility: ", max_utility
print "Total weight: ", np.sum(weights * item_indices)
for u, v in enumerate(item_indices):
    if v > 0:
        print "* ", items[u]

knapsack_exact.py

import numpy as np
import math

""" 
This is NOT the polynomial time solution (should build lookup table instead).
Clever solution with exponents (doesn't work for large utilities or big knapsack). Should switch to penalty to achieve exact fit.
"""



def knapsack(c, w, remaining_capacity, i=None):
    """
    Recursively solve the knapsack problem to maximize utility given the remaining capacity and items with weight w
    and utility c. Exactly fills the knapsack.
    :param c: vector a numpy vector of utilities
    :param w: vector a numpy vector of weights (> 0)
    :param remaining_capacity: numeric the remaining capacity in the knapsack
    :param i: none or integer used to track position in recursion
    :return: (utility, x) where x is a vector of items to include
    """
    if i is None:
        i = np.size(c) - 1

    if i < 0:
        if remaining_capacity == 0:
            return 1, np.zeros(c.shape)
        return 0, np.zeros(c.shape)

    if remaining_capacity <= 0:
        return 1, np.zeros(c.shape)

    cur_weight = w[i]

    # too heavy?
    if cur_weight > remaining_capacity:
        return knapsack(c, w, remaining_capacity, i - 1)

    # calculate utility and item list WITH item
    (utility_with_item, x_with_item) = knapsack(c, w, remaining_capacity - cur_weight, i - 1)
    utility_with_item *= math.pow(1.1, c[i])

    # calculate utility and item list WITH item
    (utility_without_item, x_without_item) = knapsack(c, w, remaining_capacity, i - 1)

    if utility_with_item > utility_without_item:
        x_with_item[i] = 1
        return utility_with_item, x_with_item

    return utility_without_item, x_without_item

items = ['map', 'compass', 'water', 'sandwich', 'glucose', 'tin', 'banana', 'apple', 'cheese', 'beer', 'suntan cream',
         'camera', 'T-shirt', 'trousers', 'umbrella', 'waterproof trousers', 'waterproof overclothes', 'note-case',
         'sunglasses', 'towel', 'socks', 'book']
utilities = np.array([150, 35, 200, 160, 60, 45, 60, 40, 30, 10, 70, 30, 15, 10, 40, 70, 75, 80, 20, 12, 50, 10])
weights = np.array([9, 13, 153, 50, 15, 68, 27, 39, 23, 52, 11, 32, 24, 48, 73, 42, 43, 22, 7, 18, 4, 30])

# solve
max_utility, item_indices = knapsack(utilities, weights, 400)

print "Max utility: ", math.log(max_utility, 1.1)
print "Total weight: ", np.sum(weights * item_indices)
for u, v in enumerate(item_indices):
    if v > 0:
        print "* ", items[u]