Python: Stuck on final piece of Knapsack Calculation

Question

I am almost done calculating my knapsack problem. I have a list of items with their weights (lbs) and value. And my knapsack cannot exceed 11 pounds.

I cannot figure out the last piece of code which would calculate and print out the following: 1. list of optimal items to bring 2. total weight 3. total value of items

Please see my current code below:

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

Any help would be greatly appreciated!

gzc gzc · Accepted Answer · 2017-03-26T11:08:04

Follow your thought, you need iterate over all combinations and pick optimal solution. BTW, this algorithm time complexity is O(2^N), very inefficient.

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)

Output:

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: Stuck on final piece of Knapsack Calculation

1 Answers