Waiting_States = #list of States waiting to be explored Root = State(0, 0, 0, *len(data_value)) #start with nothing Right_child = State(level, self.benefit, self.weight, self.token) Left_child = State(level, left_benefit, left_weight, left_token) If self.weight + data_weight <= max_weight: #if not overweighted, give left child Upperbound += data_value * (max_weight - weight_accumulate) / data_weight * self.available Upperbound += data_value * self.available Weight_accumulate += data_weight * self.available If data_weight * self.available <= max_weight - weight_accumulate: Weight_accumulate = 0 #accumulated weight used to stop the upperbound summation Self.available = self.token+*(len(data_value)-level)ĭef upperbound(self): #define upperbound using fractional knaksack #available = list marking all tasks available, i.e. means item0 token, item1 non-token, item2 non-token #token = list marking if a task is token. value/weightĭata_weight = for i in order]ĭata_value = for i in order]ĭata_item = for i in order]ĭef _init_(self, level, benefit, weight, token): #sort data based on their 'efficiency', i.e. Order = for i in sorted(enumerate(data_eff), key=lambda x:x, reverse=True)] 'note-case', 'sunglasses', 'towel', 'socks', 'book']ĭata_weight = ĭata_value = ĭata_eff = map(truediv, data_value, data_weight) from operator import truedivĭata_item = ['map', 'compass', 'water', 'sandwich', 'glucose', 'tin', 'banana',\ 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. He creates a list of what he wants to bring for the trip but the total weight of all items is too much. 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. They will go to the mountains to see the wonders of nature, so he needs to pack well for the trip.
#KNAPSACK BAG CODE#
Could you please review my code and give me some tips to improve it?Ī tourist wants to make a good trip at the weekend with his friends. But this is my first time to write this kind of code, I am feeling unconfident. I tested it with the case from Rosetta and it outputs correctly. I wrote a code in Python to solve Knapsack problem using branch and bound.
0 kommentar(er)
