Рюкзак Функция Python

Question

У меня есть этот вопрос относительно проблемы с рюкзаком, и цель в значительной степени похожа на результат проблемы с рюкзаком. Возникает вопрос:

Предположим, у вас есть коллекция п элементов. Все предметы имеют одинаковый вес, w и вы можете выбрать не более один каждого товара. Написать функцию Python, которая дана в качестве входных данных емкости рюкзака, емкости, список (отсортированный в порядке возрастания) значений, значения, каждый элемент, и вес, ж и возвращает максимальное значение, которое может содержать рюкзак.

Я попытался написать функцию, но почему-то не мог понять, где бы вес, w, будет подходящим в строке кода.

def knapsack(capacity,n): 
    if len(n) ==0: 
      return 0 
    elif n[-1][0] > capacity: 
      return knapsack(capacity, n[:-1]) 
    else: 
      return max(knapsack(capacity,n[:-1]), knapsack(capacity-n[-1][0],n[:-1]+n[-1][1] 

Каким-то образом, я искал много способов, чтобы выяснить этот вопрос, как я относительно новым для Python, но мне не понравилось, как код работает, как я не понял, вопрос полностью , Есть ли лучший способ решить эту функцию Python?

Answer 1

Если все они имеют одинаковый вес, это делает проблему довольно тривиальной.

Вам просто нужно отсортировать предметы по их значению в порядке убывания и начать выбирать элементы из списка, пока у вас не будет больше элементов в списке значений, или у вас не хватило емкости для хранения большего количества.

Обратите внимание, что проблема заключается в том, что значения сортируются в порядке возрастания. Поскольку список уже отсортирован в порядке возрастания, вы можете просто перевернуть список, чтобы элементы отображались в порядке убывания значения. Это даст вам элемент с наибольшим значением в первую очередь.

Начиная с первого элемента, продолжайте выбирать предметы, пока вы больше не сможете их поместить в свой рюкзак.

def knapsack(capacity, values): 
    values.reverse() 
    num_items = capacity // w 
    return sum(values[:num_items]) 

num_items имеет максимальное количество элементов, которые мы можем поместиться в рюкзаке. values[:num_items] использует массивы для извлечения наименьших значений num_items из массива, затем, наконец, мы передаем это функции sum для вычисления максимальной суммы