Please help understand. The capacity of the backpack is 6 (say, kg), you need to fit the maximum number of items into it, getting the most favorable result (max profit). I understand that 1 and 4 or 2 and 3 items should fall into the backpack.

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

3 answers 3

The 0-1 backpack problem can be solved using dynamic programming - O(n W) in time and memory algorithm:

  1. We start with an empty backpack (the allowed weight is equal to the full capacity of the backpack — W ) and all items (all n items are available).
  2. If the greatest value that can be obtained using all available items (indexes not more than specified) is greater than the value that can be obtained, not including the current item (with the largest index), then
    • add current item to result
    • reduce the allowed weight by an amount equal to the weight of the current object
  3. Repeat step number 2, excluding the item with the highest index from the list of available items, while there are still available items.

Where the greatest value is determined by the recurrence relations :

  • if there are no items available, then the greatest value is zero
  • if the weight of the current item is greater than the allowed weight, then the result is equal to the greatest value without this item (with the remaining n-1 available items)

  • otherwise, choose a maximum of two options:

    (a) option that excludes current item
    (b) a variant that includes the current item. The greatest value in this case is equal to the sum of the value of the current item and the greatest value of the remaining available items with the allowed weight reduced by the weight of the current item (less space left in the backpack).

Recursive Python solution :

 #!/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())

Result

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

    In my opinion the word goods is only used in the plural ...

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

    Conclusion:

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

    degree acts as a limiter of the number of objects, and how much the same object can be repeated when stuffed into a backpack.

    If you need ak2 p2 + p3 / p3 + p2 without duplicates, then there is a condition before append , you need to sort ss - if tuple(sorted(ss))

      Decision on the issue

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

      General case solution

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

      elements must be a sequence of pairs (weight, value), where max_w is the maximum possible weight.

      • one
        Dear, this is Russian SO, answers in other languages ​​are unacceptable here. - freim
      • If you use source data different from the data in the question, explain briefly how your decision answers the TS question. - 0xdb
      • Thanks, remarks taken into account - Arslan Tarlanov