파이썬 : 배낭 계산의 마지막 부분에 붙이기

Question

거의 배낭 문제를 계산했습니다. 나는 그들의 무게 (lbs)와 가치를 가진 품목의 목록을 가지고있다. 그리고 내 배낭은 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

모든 조합에 대해 반복하고 최적의 솔루션을 선택해야합니다. BTW,이 알고리즘 시간 복잡도는 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))