Python代码中允许使用递归函数计算最大行李量

Question

我是python新手，我有一个任务，我需要写一个递归函数，它有两个参数（Weights，W），Weights是行李的重量列表，W是学生可以携带的最大重量，在python 2.7中，它计算学生可以携带的最大行李量，并且不超过最大限制（W），例如，如果：

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

这是我的代码，但它返回错误：

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()

错误消息：

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)

我完全不确定我的代码我认为这是完全错误的

权重是权重列表，W是最大权重。
鉴于此，我想知道weights[]列表中有多少项可以带上飞机。
*我无法更改带两个参数的函数calc_max_baggage(weights, W)。

W也可以是负数，在这种情况下，函数返回0。你知道吗

必须仅使用递归进行求解，而不使用循环

谢谢

Answer 1

我们可以稍微修改来自itertools doumentation的powerset配方，以不使用显式循环：

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)))

对于每一种行李组合，我们可以过滤掉所有超过最大重量的行李，然后选择物品最多的一件：

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, ((),))是这样的，如果W是负数，我们无论如何都不会返回任何行李，即使从技术上讲，它们的重量之和大于W。你知道吗

这将返回实际的项目集，而不是它的长度，但是您可以轻松地转换它。你知道吗

>>> 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)
()

如果您需要一个递归组件，可以递归地定义powerset，尽管效率明显较低

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