Python：卡在背包计算的最后一块

Question

我快完成背包问题的计算了。我有一份物品清单，上面有重量（磅）和价值。而且我的背包不能超过11磅

我想不出最后一段代码会计算并打印出以下内容： 1.最佳携带物品清单 2.总重量 3.物品总价值

请在下面查看我当前的代码：

# Potential items to bring in knapsack 

items = (
    ("t-shirt", 0.53, 15), 
    ("trousers", 1.06, 10), 
    ("waterproof trousers", 0.93, 70), 
    ("waterproof overclothes", 0.95, 75),
    ("socks", 0.09, 50), 
    ("backpack & gear packaging", 1.9, 300), 
    ("sleeping gear & tent/shelter", 2.8, 260), 
    ("hammock", 2.8, 120),
    ("cooking gear & water storage", 0.8, 240),
    ("map", 0.2, 150), 
    ("compass", 0.29, 35), 
    ("glucose", 0.33, 60), 
    ("tin", 1.5, 45),
    ("sunscreen", 0.24, 70), 
    ("first aid kit", 1.3, 90), 
    ("umbrella", 1.61, 40), 
    ("water (1 pint)", 1, 200),
    ("food (3 days)", 4.5, 190), 
    ("fuel", 0.2, 190), 
    ("camera", 0.71, 30),
    ("beer", 1.15, 10), 
    ("towel", 0.4, 12),
    ("book", 0.66, 10),
    ("sunglasses", 0.15, 20),
    ("notebook", 0.49, 80)
)

from itertools import combinations

def combinations_func(items):
    """ return any combination from list of potential items for knapsack """ 
    return (combination
            for r in range(1, len(items)+1)
            for combination in combinations(items, r))

def totalvalue_func(combination):
    """ calculate total value for a combination of knapsack items """
    total_weight = 0
    total_value = 0
    for item, weight, value in combination:
        total_weight += weight
        total_value += value 
    return (total_value, -total_weight) if total_weight <= 11 else (0,0)

如有任何帮助，我们将不胜感激！

Answer 1

按照您的想法，您需要迭代所有组合并选择最佳解决方案。顺便说一句，这个算法的时间复杂度是O(2^N)，非常低效。

max_value = -float('Inf')
weight = None
optimal_items = None
for comb in combinations_func(items):
    total_value, total_weight = totalvalue_func(comb)
    if total_value > max_value:
        max_value = total_value
        weight = total_weight
        optimal_items = comb

print(max_value)
print(weight)
print(optimal_items)

输出：

1820
10.74
(('waterproof overclothes', 0.95, 75), ('socks', 0.09, 50), ('backpack & gear packaging', 1.9, 300), ('sleeping gear & tent/shelter', 2.8, 260), ('cooking gear & water storage', 0.8, 240), ('map', 0.2, 150), ('compass', 0.29, 35), ('glucose', 0.33, 60), ('sunscreen', 0.24, 70), ('first aid kit', 1.3, 90), ('water (1 pint)', 1, 200), ('fuel', 0.2, 190), ('sunglasses', 0.15, 20), ('notebook', 0.49, 80))

Python：卡在背包计算的最后一块

Python: Stuck on final piece of Knapsack Calculation

python

printing

function

knapsack-problem