solving a knapsack problem

packing_my_robot_body.py

#! /usr/bin/env python

import json
import requests
import click

def read_description(url):
    """Read json from url.

    :param url: url to access
    :return: dict on success, else {}"""
    res = requests.get(url)
    if res.status_code != 200:
        click.secho("Failed to get response from %s." % url,fg='red')
        click.secho("%s" % res.text)
        return {}

    try:
        data = res.json()
    except ValueError:
        click.secho("Failed to parse response from %s." % url, fg='red')
        click.secho("%s" % res.text)
        return {}
    return data

def get_selection(table, parts, capacity=None):
    """Backtracks the table for the best items.

    :param table: table created by create_lookup_table(...)
    :param parts: list of parts used to create table
    :param capacity: None or int value < len(table[0])
    :returns: dict with list of item ids and the total value
    """
    i = len(table)-1
    v = capacity or len(table[0])-1
    selected = []
    while (i>0) and (v>0):
        item = parts[i-1]
        if table[i][v] != table[i-1][v]:
            selected.append(item)
            v = v - item['value']
        i -= 1
    return {
        "part_ids": [ x['id'] for x in selected ],
        "value": table[-1][-1]
    }

def show_table(table):
    """Display the matrix using matplotlib."""

    # I have put the imports here so installing them is optional
    import numpy as np
    import matplotlib.pyplot as plt
    plt.imshow(np.array(table),aspect='auto',interpolation='nearest')
    plt.show()

def create_lookup_table(capacity, parts):
    """Use dynamic programming to build a lookup table.

    Creates a (N+1)x(C+1) integer matrix, where N is the number of parts
    and C the max capacity of the suitecase. The best value of all items
    for a certain capacity is stored at table[N][C]. First column and row
    are kept as 0.

    Details about this implementation can be found here:
    https://bruceoutdoors.wordpress.com/2015/12/14/1-0-knapsack-problem-a-hands-on-guide-c/

    :param capacity: max capacity of the suitecase as integer
    :param parts: list of items as dicts with keys 'value' and 'volume'
    :returns: table of values as list of lists
    """
    table = [ [0]*int(capacity+1) for i in range(len(parts)+1) ]
    for i in range(1,len(table)):
        item = parts[i-1]
        for v in range(1,len(table[0])):
            if item['volume'] > v:
                table[i][v] = table[i-1][v]
            else:
                table[i][v] = max(
                    table[i-1][v],
                    table[i-1][v-item['volume']] + item['value'])
    return table

@click.command()
@click.argument('suitecase_url')
@click.argument('parts_url')
@click.option('--display', is_flag=True, help="Show table using matplotlib")
def cli(suitecase_url, parts_url, display):
    """CLI to calculate the most valuable body parts.

    Expects response from urls as json.

    \b
    :param suitecase_url: url to suitecase description
    :param parts_url: url to parts description
    """
    suitecase = read_description(suitecase_url)
    if not suitecase:
        exit(-1)
    parts = read_description(parts_url)
    if not parts:
        exit(-1)

    #suitecase = {'volume': 7}
    #parts = [
    #    {'volume':3,'value':4,'id':0},
    #    {'volume':5,'value':7,'id':1},
    #    {'volume':1,'value':1,'id':2},
    #    {'volume':4,'value':5,'id':3},]

    table = create_lookup_table(suitecase['volume'], parts)
    print(json.dumps(get_selection(table, parts),indent=4))
    if display:
        show_table(table)

if __name__ == '__main__':
    cli()