Код Python для расчета максимального количества багажа допускается с использованием рекурсивной функции - PullRequest
Новая
       7

Код Python для расчета максимального количества багажа допускается с использованием рекурсивной функции

0 голосов
/ 14 декабря 2018

Я новичок в python, и у меня есть задание, мне нужно написать рекурсивную функцию, которая принимает два аргумента (Вес, W), вес - это список весов багажа, а 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 (последний вызов был последним): файл "", строка 1, в calc_max_baggage ([5], 0) файл "C: / Users / user"/ Desktop / לימודים / פייתון Python / עבודות בית / ex6 / test_ex6.py ", строка 12, в calc_max_baggage return calc_max_baggage () TypeError: calc_max_baggage () принимает ровно 2 аргумента (0 дано)

*я совершенно не уверен в своем коде, я думаю, что он абсолютно неправильный

Вес - это список весов, а W - максимальный вес.
Учитывая это, я хочу знать, сколько предметов из весов[] список можетбыть доставленным на самолет.
* Я не могу изменить функцию calc_max_baggage(weights, W), которая принимает два аргумента.

W также может быть отрицательной, в этом случаефункция возвращает 0.

ЭТО ДОЛЖНО БЫТЬ РЕШЕНО ТОЛЬКО С РЕКУРСИЕЙ И БЕЗ ЦИКЛОВ

Спасибо

1 Ответ

0 голосов
/ 14 декабря 2018

Мы можем немного изменить рецепт powerset из документации itertools , чтобы не использовать явный цикл: 

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