Python code to calculate the maximal amount of baggage is allowed using recursive function

Question

I am new to python and I have an assignment, I need to write a recursive function that takes two arguments (Weights, W), weights is the list of weights of baggage and W is the maximal weight a student can take, in python 2.7 that calculates the maximal amount of baggage a student can take and does not pass the maximal limit (W), for example if:

>>> calc_max_baggage([5], 0)
>>> 0
>>> calc_max_baggage ([1, 1, 1], 5)
>>> 3
>>> calc_max_baggage([4, 2, 3, 1], 5)
>>> 2

This is my code but it returns error:

def calc_max_baggage (weights, W):
weights = []
res = []
W = int
def number_of_index(weights, W, i): 
    if max(weights) > W:
        return res
    else:
        count += i in weights

return calc_max_baggage()

Error message:

Traceback (most recent call last): File "", line 1, in calc_max_baggage ([5], 0) File "C:/Users/user/Desktop/???????/?????? Python/?????? ???/ex6/test_ex6.py", line 12, in calc_max_baggage return calc_max_baggage() TypeError: calc_max_baggage() takes exactly 2 arguments (0 given)

I am totally not sure about my code I think its totally wrong

Weights is the list of weights and W is the maximal weight.
Given this, I want to know how many items from the weights[] list can be brought on the plane.
*I can't change the funtion calc_max_baggage(weights, W) that takes two arguments.

W can also be negative, in that case the function returns 0.

IT MUST BE SOLVED WITH RECURSION ONLY AND WITHOUT LOOPS

Thanks

Answer 1

We can slightly modify the powerset recipe from the itertools doumentation to not use an explicit loop:

from itertools import chain, combinations

def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(map(lambda r: combinations(s, r), range(len(s)+1)))

For each combination of luggage, we can filter out all of those that exceed the maximum weight, then take the one with the most items:

def calc_max_baggage(weights, W):
    weights = powerset(weights)
    filtered = filter(lambda items: sum(items) <= W, weights)
    filtered = chain(filtered, ((),)) 
    return max(filtered, key=len)

filtered = chain(filtered, ((),)) is so if W is negative we return no bags anyways, even though technically the sum of their weights is greater than W.

This will return the actual set of items, rather than its length, but you can easily convert it.

>>> calc_max_baggage([4, 2, 3, 1], 5)
(4, 1)
>>> calc_max_baggage ([1, 1, 1], 5)
(1, 1, 1)
>>> calc_max_baggage([5], 0)
()

If you need a recursive component, you can define powerset recursively, though it's markedly less efficient

def powerset(seq):
    if not seq:
        return ((),)
    else:
        head, *tail = seq
        tail_pow = powerset(tail)
        with_head = tuple(map(lambda t: (head,) + t, tail_pow))
        return with_head + tail_pow