CS 61A

Structure and Interpretation of Computer Programs, Fall 2014

Instructor: John DeNero




Question | Knapsack

You’re are a thief, and your job is to pick among n items that are of different weights and values. You have a knapsack that supports ‘c’ pounds, and you want to pick some subset of the items so that you maximize the value you’ve stolen.

Define knapsack, which takes a list weights, list values and a capacity c, and returns that max value. You may assume that item 0 weighs weights[0] pounds, and is worth values[0]; item 1 weighs weights[1] pounds, and is worth values[1]; etc.

def knapsack(weights, values, c):
    """
    >>> w = [1.5, 4, 3, 3]
    >>> v = [1, 5, 2, 3]
    >>> knapsack(w, v, 6)
    6
    """
    ## YOUR CODE HERE ##

def knapsack(weights, values, c):

""" 
>>> w = [2, 6, 3, 3]
>>> v = [1, 5, 3, 3]
>>> knapsack(w, v, 6)
6
"""
if weights == []: 
    return 0
else:
    first_weight, rest_weights = weights[0], weights[1:]
    first_value, rest_values = values[0], values[1:]
    with_first = first_value + knapsack(rest_weights, rest_values, c-first_weight)
    without_first = knapsack(rest_weights, rest_values, c)
    if first_weight <= c:
        return max(with_first, without_first)
    return without_first