Python FlightItem

Create a new class named FlightItem by extending Item class in the Jupyter notebook handed out as the part of the lecture.

Add following data attributes

• departure
• destination
• travel_distance
• travel_time
• air_fare

Within its constructor (__init__ method):

• Assign value attribute as travel_distance / air_fair.
• Set the weight equal to travel_time

Modify build_items() function to use the following data to initialize item list with FlightItem objects:

• names = ['flight 111', 'flight 222', 'flight 333', 'flight 444', 'flight 555', 'flight 656', 'flight 777']
• departure = ['ALB', 'BWI', 'BOS', 'DEN', 'DFW', 'LAX', 'SFO' ]
• destination = ['DFW', 'SFO', 'SFO', ' LAX ', BWI', 'DFW', 'DEN' ]
• travel_distance = [1650, 2825, 3106, 1056, 1381, 1443, 1258]
• travel_time = [120, 300, 360, 180, 150, 90, 110]
• air_fare = [200.00, 300.00, 650.00, 150.00, 220.00, 315.00, 300.00]

Run test_greedys() function and provide the output.

Item

# Greedy Algorithms
class Item(object):
def __init__(self, n, v, w):
self.name = n
self.value = v
self.weight = w

def get_name(self):
return self.name

def get_value(self):
return self.value

def get_weight(self):
return self.weight

def __str__(self):
result = '<' + self.name + ', ' + str(self.value)
+ ', ' + str(self.weight) + '>'
return result

def value(item):
return item.get_value()

def weight_inverse(item):
return 1.0 / item.get_weight()

def density(item):
return item.get_value() / item.get_weight()

Greedy

# Greedy Algorithm Implementation
def greedy(items, max_weight, key_function):
"""Assumes items a list, max_weight >= 0,
key_function maps elements of items to numbers"""
items_copy = sorted(items, key=key_function, reverse=True)
result = []
total_value, total_weight = 0.0, 0.0
for i in range(len(items_copy)):
if (total_weight + items_copy[i].get_weight()) <= max_weight:
result.append(items_copy[i])
total_weight += items_copy[i].get_weight()
total_value += items_copy[i].get_value()
return (result, total_value)

Test Greedys

def test_greedys(max_weight = 20):
items = build_items()
print('Use greedy by value to fill knapsack of size', max_weight)
test_greedy(items, max_weight, value)
print('\nUse greedy by weight to fill knapsack of size', max_weight)
test_greedy(items, max_weight, weight_inverse)
print('\nUse greedy by density to fill knapsack of size', max_weight)
test_greedy(items, max_weight, density)