Python Knapsack problem using branch and bound algorithm

I wrote a code in Python to solve Knapsack problem using branch and bound. I tested it with the case from Rosetta and it outputs correctly. But this is my first time to write this kind of code, I am feeling unconfident. Could you please review my code and give me some tips to improve it?


A tourist wants to make a good trip at the weekend with his friends. They will go to the mountains to see the wonders of nature, so he needs to pack well for the trip. He has a good knapsack for carrying things, but knows that he can carry a maximum of only 4kg in it and it will have to last the whole day. He creates a list of what he wants to bring for the trip but the total weight of all items is too much. He then decides to add columns to his initial list detailing their weights and a numerical value representing how important the item is for the trip.

```
from operator import truediv
data_item = ['map', 'compass', 'water', 'sandwich', 'glucose', 'tin', 'banana',\
'apple', 'cheese', 'beer', 'suntan', 'camera', 'T', 'trousers', 'umbrella', 'w t', 'w o', \
'note-case', 'sunglasses', 'towel', 'socks', 'book']
data_weight = [9, 13, 153, 50, 15, 68, 27, 39, 23, 52, 11, 32, 24, 48, 73, 42, 43, 22, 7, 18, 4, 30]
data_value = [150, 35, 200, 160, 60, 45, 60, 40, 30, 10, 70, 30, 15, 10, 40, 70, 75, 80, 20, 12, 50, 10]
data_eff = map(truediv, data_value, data_weight)
order = [i[0] for i in sorted(enumerate(data_eff), key=lambda x:x[1], reverse=True)]
#sort data based on their 'efficiency', i.e. value/weight
data_eff = [data_eff[i] for i in order]
data_weight = [data_weight[i] for i in order]
data_value = [data_value[i] for i in order]
data_item = [data_item[i] for i in order]
max_weight = 400

class State(object):
def __init__(self, level, benefit, weight, token):
#token = list marking if a task is token. ex. [1, 0, 0] means item0 token, item1 non-token, item2 non-token
#available = list marking all tasks available, i.e. not explored yet
self.level = level

Instead of sorting values, taking the corresponding indices and using them to have the values of a different array in the order of your choice, you could generate tuples containing all the relevant information (name, weight, value) and sort them with a function of your choice.

This reduces :

data_eff = map(truediv, data_value, data_weight)
order = [i[0] for i in sorted(enumerate(data_eff), key=lambda x:x[1], reverse=True)]
#sort data based on their 'efficiency', i.e. value/weight
data_eff = [data_eff[i] for i in order]
data_weight = [data_weight[i] for i in order]
data_value = [data_value[i] for i in order]
data_item = [data_item[i] for i in order]

to a more efficient and more concise :

data_sorted = sorted(zip(data_item, data_weight, data_value), key=lambda (i,w,v):v//w, reverse=True)

You could them split this into 3 arrays but I am not sure it is worth the pain.

Indeed, a few things can be done in a more concise way now like :

for i, (item, w, v) in enumerate(data_sorted):
    if w * self.available[i] <= max_weight - weight_accumulate:
        weight_accumulate += w * self.available[i]
        upperbound += v * self.available[i]
    else:
        upperbound += v * (max_weight - weight_accumulate) / w * self.available[i]
        break

and re-improved using zip :

for avail, (item, w, v) in zip(self.available, data_sorted):
    if w * avail <= max_weight - weight_accumulate:
        weight_accumulate += w * avail
        upperbound += v * avail
    else:
        upperbound += v * (max_weight - weight_accumulate) / w * avail
        break

Also,

best_solution = current_state
best_item = []
for i in range(len(best_solution.token)):
    if (best_solution.token[i] == 1):
        best_item.append(data_item[i])

can be rewritten using zip list comprehension and the data_sorted array defined previously :

best_item = [item for tok, (item, _, _) in zip(current_state.token, data_sorted) if tok == 1]

Now, to comment on the style, you should use is to compare to None as per the style guide PEP8.

After changing these and many other details (provided by the tool pep8 checking for various style issues such as spacing, line length, etc), I end up with :

```
data_item = ['map', 'compass', 'water', 'sandwich', 'glucose', 'tin', 'banana',
'apple', 'cheese', 'beer', 'suntan', 'camera', 'T', 'trousers',
'umbrella', 'w t', 'w o', 'note-case', 'sunglasses', 'towel',
'socks', 'book']
data_weight = [9, 13, 153, 50, 15, 68, 27, 39, 23, 52, 11, 32, 24, 48, 73, 42,
43, 22, 7, 18, 4, 30]
data_value = [150, 35, 200, 160, 60, 45, 60, 40, 30, 10, 70, 30, 15, 10, 40,
70, 75, 80, 20, 12, 50, 10]
data_sorted = sorted(zip(data_item, data_weight, data_value),
key=lambda (i, w, v): v//w, reverse=True)

max_weight = 400

class State(object):
def __init__(self, level, benefit, weight, token):
# token = list marking if a task is token. ex. [1, 0, 0] means
# item0 token, item1 non-token, item2 non-token
# available = list marking all tasks available, i.e. not explored yet
self.level = level
self.benefit = benefit
self.weight = weight
self.token = token
self.available = self.token[:self.level]+[1]*(len(data_sorted)-level)
self.ub = self.upperbound()

def upperbound(self): # define upperbound using fractional knaksack
upperbound = 0 # initial upperbound
# accumulated weight used to stop the upperbound summation
weight_accumulate = 0
for avail, (_, wei, val) in zip(self.available, data_sorted):
if wei * avail <= max_weight - weight_accumulate:
weight_accumulate += wei * avail
upperbound += val * avail
else:
upperbound += val (max_weight - weight_accumulate) / wei avail
break
return upperbound

def develop(self):
level = self.level + 1
_, weight, value = data_sorted[self.level]
left_weight = self.weight + weight
if left_weight <= max_weight: # if not overweighted, give left child
left_benefit = self.benefit + value
left_token = self.token[:self.level]+[1]+self.token[level:]
left_child = State(level, left_benefit, left_weight, left_token)
else:
left_child = None
# anyway, give right child
right_child = State(level, self.benefit, self.weight, self.token)
return ([] if left_child is None else [left_child]) + [right_child]

Root = State(0, 0, 0, [0] * len(data_sorted)) # start with nothing
waiting_States = [] # list of States waiting to be explored
current_state = Root
while current_state.level < len(data_sorted):
waiting_States.extend(current_state.develop())
# sort the waiting list based on their upperbound
waiting_States.sort(key=lambda x: x.ub)
# explore the

StackExchange Code Review Q#94428, answer score: 5