TheAlgorithms-Python
63 строки · 1.9 Кб
1class Things:2def __init__(self, name, value, weight):3self.name = name4self.value = value5self.weight = weight6
7def __repr__(self):8return f"{self.__class__.__name__}({self.name}, {self.value}, {self.weight})"9
10def get_value(self):11return self.value12
13def get_name(self):14return self.name15
16def get_weight(self):17return self.weight18
19def value_weight(self):20return self.value / self.weight21
22
23def build_menu(name, value, weight):24menu = []25for i in range(len(value)):26menu.append(Things(name[i], value[i], weight[i]))27return menu28
29
30def greedy(item, max_cost, key_func):31items_copy = sorted(item, key=key_func, reverse=True)32result = []33total_value, total_cost = 0.0, 0.034for i in range(len(items_copy)):35if (total_cost + items_copy[i].get_weight()) <= max_cost:36result.append(items_copy[i])37total_cost += items_copy[i].get_weight()38total_value += items_copy[i].get_value()39return (result, total_value)40
41
42def test_greedy():43"""44>>> food = ["Burger", "Pizza", "Coca Cola", "Rice",
45... "Sambhar", "Chicken", "Fries", "Milk"]
46>>> value = [80, 100, 60, 70, 50, 110, 90, 60]
47>>> weight = [40, 60, 40, 70, 100, 85, 55, 70]
48>>> foods = build_menu(food, value, weight)
49>>> foods # doctest: +NORMALIZE_WHITESPACE
50[Things(Burger, 80, 40), Things(Pizza, 100, 60), Things(Coca Cola, 60, 40),
51Things(Rice, 70, 70), Things(Sambhar, 50, 100), Things(Chicken, 110, 85),
52Things(Fries, 90, 55), Things(Milk, 60, 70)]
53>>> greedy(foods, 500, Things.get_value) # doctest: +NORMALIZE_WHITESPACE
54([Things(Chicken, 110, 85), Things(Pizza, 100, 60), Things(Fries, 90, 55),
55Things(Burger, 80, 40), Things(Rice, 70, 70), Things(Coca Cola, 60, 40),
56Things(Milk, 60, 70)], 570.0)
57"""
58
59
60if __name__ == "__main__":61import doctest62
63doctest.testmod()64