What did I do wrong?

Brute-Force Optimization

Starting from the knapsack problem (the coin or souvenir example), rewrite (simplify) it to consider the given weights

[ 6,7,3,4,5,2,2,1,8 ]

and the values

[ 5,6,3,3,4,1,1,2,9 ]

(Note that there are nine items now instead of ten.)

Retain the same figure of merit, except that the total weight can be 20 instead of 50. Identify the subset of items (indices) max_set which maximizes value with that constraint.

Starter Code:

# Set up the problem. import numpy as np n = 10 items = list( range( n ) ) weights = np.random.uniform( size=(n,) ) * 50 values = np.random.uniform( size=(n,) ) * 100 # Define a figure of merit. def f( wts, vals ): total_weight = 0 total_value = 0 for i in range( len( wts ) ): total_weight += wts[ i ] total_value += vals[ i ] if total_weight >= 50: return 0 else: return total_value # Solve the problem by trying all combinations. import itertools max_value = 0.0 max_set = None for i in range(n): for set in itertools.combinations( items,i ): wts = [] vals = [] for item in set: wts.append( weights[ item ] ) vals.append( values[ item ] ) value = f( wts,vals ) if value > max_value: max_value = value max_set = set

my code:

# Set up the problem. import numpy as np

n = 10 items = list( range( n ) ) weights = np.random.uniform( size=(n,) ) * 50 values = np.random.uniform( size=(n,) ) * 100

# Define a figure of merit. def f( wts, vals ): total_weight = 0 total_value = 0

for i in range( len( wts ) ): total_weight += wts[ i ] total_value += vals[ i ]

if total_weight >= 50: return 0 else: return total_value

# Solve the problem by trying all combinations. import itertools

max_value = 0.0 max_set = None for i in range(n): for set in itertools.combinations( items,i ): wts = [] vals = [] for item in set: wts.append( weights[ item ] ) vals.append( values[ item ] ) value = f( wts,vals ) if value > max_value: max_value = value max_set = set

error:

Your final set doesn't seem to have the correct number of elements.

Are any arrays the correct sizes, and are you not trying to use them with any `if` statements?

Execution time: 0.1 s -- Time limit: 10.0 s