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

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

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