2

Прошу помочь разобраться. Вместимость рюкзака — 6 (допустим, кг), необходимо вместить в него максимальное количество предметов, получив максимально выгодный результат (макс profit). Я понимаю, что в рюкзак должны попасть 1 и 4 или 2 и 3 предметы.

from collections import namedtuple

Good = namedtuple('Good', ['profit', 'weight'])
goods = [Good(4, 5), Good(3, 4), Good(3, 2), Good(2, 1)]  # sample data
capacity = 6

def calc_profit(goods, capacity):
    s_goods = sorted(goods)
    items = capacity  // s_goods
    return sum(goods[:items])
2

3 ответа 3

2

Задачу о рюкзаке 0-1 можно решить,используя динамическое программирование — O(n W) по времени и памяти алгоритм:

  1. Начинаем с пустого рюкзака (разрешённый вес равен полной ёмкости рюкзака— W) и всех предметов (все n предметов доступны).
  2. Если наибольшая ценность, которую можно получить, используя все доступные предметы (индексы не более заданного), больше ценности, которую можно получить, не включая текущий предмет (с наибольшим индексом), то
    • добавляем текущий предмет в результат
    • уменьшаем разрешённый вес на величину равную весу текущего предмета
  3. Повторяем шаг №2, исключая предмет с наибольшим индексом из списка доступных предметов, пока всё ещё остались доступные предметы.

Где наибольшая ценность определяется рекуррентными соотношениями:

  • если нет доступных предметов, то наибольшая ценность равна нулю
  • если вес текущего предмета больше разрешённого веса, то результат равен наибольшей ценности без этого предмета (c оставшимися n-1 доступными предметами)
  • в противном случае, выбираем максимум из двух вариантов:

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

Рекурсивное решение на Питоне:

#!/usr/bin/env python3
"""0-1 knapsack problem: O(n W) in time, space algorithm"""
from collections import namedtuple
from functools import lru_cache

Item = namedtuple('Item', 'value weight')
items = Item(4, 5), Item(3, 4), Item(3, 2), Item(2, 1)
capacity = 6  # max weight we can put into the knapsack


@lru_cache(maxsize=None)  # cache all calls
def best_value(nitems, weight_limit):
    if nitems == 0:  # no items
        return 0  # zero value
    elif items[nitems - 1].weight > weight_limit:
        # new item is heavier than the current weight limit
        return best_value(nitems - 1, weight_limit)  # don't include new item
    else:
        return max(  # max of with and without the new item
            best_value(nitems - 1, weight_limit),  # without
            best_value(nitems - 1, weight_limit - items[nitems - 1].weight)
            + items[nitems - 1].value)  # with the new item


result = []
weight_limit = capacity
for i in reversed(range(len(items))):
    if best_value(i + 1, weight_limit) > best_value(i, weight_limit):
        # better with the i-th item
        result.append(items[i])  # include it in the result
        weight_limit -= items[i].weight
print(result)
print(best_value.cache_info())

Результат

[Item(value=3, weight=2), Item(value=3, weight=4)]
CacheInfo(hits=9, misses=21, maxsize=None, currsize=21)
1

По-моему слово goods только в множественном числе используется...

from itertools import permutations
goods = (("p1", 4), ("p2", 3), ("p3", 3), ("p4", 2))
max_capacity = 6
max_degree = max_capacity / min([x[1] for x in goods])
result = []
for degree in range(1, max_degree + 1):
    for ss in permutations(goods * degree, degree):
        if ss not in result and sum(map(lambda y: y[1], list(ss))) == 6:
            result.append(ss)
for i in result:
    print " + ".join(map(lambda z: z[0], list(i)))

Вывод:

p1 + p4
p2 + p3
p2 + p2
p3 + p2
p3 + p3
p4 + p1
p4 + p4 + p4

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

Если нужно без дублей аки p2 + p3 / p3 + p2, то там условие перед append, нужно отсортировать ss - if tuple(sorted(ss))

0

Решение по вопросу

from itertools import combinations
from collections import namedtuple

Good = namedtuple('Good', ['profit', 'weight'])
goods = [Good(4, 5), Good(3, 4), Good(3, 2), Good(2, 1)]  # sample data
capacity = 6

print(max(filter(lambda x: sum(list(zip(*x))[0]) <= capacity, (v for r in range(1, len(goods)) for v in combinations(filter(lambda x: x[0] <= capacity, goods), r))), key=lambda x: sum(list(zip(*x))[1])))

Решение для общего случая

from itertools import combinations

max_w = 15
items = [(12, 4), (1, 2), (4, 6), (1, 1), (2, 2)]  # (11, [(1, 2), (4, 6), (1, 1), (2, 2)])

print(max(filter(lambda x: sum(list(zip(*x))[0]) <= max_w, (v for r in range(1, len(items)) for v in combinations(filter(lambda x: x[0] <= max_w, items), r))), key=lambda x: sum(list(zip(*x))[1])))

элементы должны быть последовательностью пар (вес, значение), где max_w - максимальный возможный вес.

3
  • 1
    Уважаемый, это русский SO, ответы на других языках здесь неприемлемы.
    – freim
    28 мая 2019 в 11:43
  • Если вы используете исходные данные отличающиеся от данных в вопросе, поясните коротко, как ваше решение отвечает на вопрос ТС.
    – 0xdb
    28 мая 2019 в 11:53
  • Спасибо, замечания учел 29 мая 2019 в 14:06

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.