root/hodgestar/PythonCode/SmallScripts/knap.py

"""Help our clients spend as much of their vouchers as possible.

One-over-N click shopping.
"""


def raw_knap(i, W, w, v):
    """Calculate m[i, W].

    Parameters
    ----------
    i : int
        Consider only first i items of w.
    W : float
        Maximum weight the sack can hold.
    w : list of floats
        Weights of items we're trying to put in the sack.
    v : list of floats
        Values of items we're trying to put in the sack.

    Return
    ------
    max_value : float
        Maximum value.
    max_weight : float
        Weight of items that make up maximum value.
    items : list of int
        List of items from w that make up maxw.
    """
    if i == 0:
        return 0, 0, []
    elif W <= 0:
        return 0, 0, []
    else:
        max_v, max_w, items = raw_knap(i-1, W, w, v)
        vi, wi = v[i-1], w[i-1]
        if wi <= W:
            max_vi, max_wi, items_i = raw_knap(i-1, W-wi, w, v)
            if max_vi + vi > max_v:
                max_v, max_w, items = max_vi + vi, max_wi + wi, items_i + [i-1]
        return max_v, max_w, items


def knap(w, W):
    """Calculate maximum weight of items for w than can fit into W.

    Parameters
    ----------
    w : list of floats
        Items we're trying to put in the sack.
    W : float
        Maximum weight the float can hold.

    Return
    ------
    max_weight : float
        Maximum weight.
    items : list of float
        List of items from w that make up maxw.
    """
    result = raw_knap(len(w), W, w, w)
    return result[0], result[2]