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