A greedy algorithm chooses a locally optimal option at each step in the hope of reaching a globally optimal solution. Its choices are guided by a heuristic, and the approach can fail to find the global optimum. section 4.2.2
A greedy approach typically:
- Defines a heuristic for ranking available choices, then selects the best-ranked option at each step. section 4.2.2
- Can be used for sensor placement by repeatedly adding the sensor with the largest information gain; under stated independence conditions, submodularity supports efficient algorithms with performance guarantees. section 4.2.2
Fractional knapsack
For a knapsack of capacity W, rank items by value-to-weight ratio. Because fractions are allowed, fill remaining capacity with part of the next item. In the worked result, taking items 1 and 2 and two-thirds of item 3 gives a total value of 240; sorting makes the algorithm O(n log n). section 4.2.2
Listing 4.2 Fractional knapsack
class Item:
def __init__(self, wt, val, ind):
self.wt = wt
self.val = val
self.ind = ind
self.cost = val // wt
def __lt__(self, other):
return self.cost < other.cost
class FractionalKnapSack:
def get_max_value(self, wt, val, capacity):
item_list = []
for i in range(len(wt)):
item_list.append(Item(wt[i], val[i], i))
# sorting items by cost heuristic
item_list.sort(reverse = True) #O(nlogn)
total_value = 0
for i in item_list:
cur_wt = int(i.wt)
cur_val = int(i.val)
if capacity - cur_wt >= 0:
capacity -= cur_wt
total_value += cur_val
else:
fraction = capacity / cur_wt
total_value += cur_val * fraction
capacity = int(capacity - (cur_wt * fraction))
break
return total_value
if __name__ == "__main__":
wt = [10, 20, 30]
val = [60, 100, 120]
capacity = 50
fk = FractionalKnapSack()
max_value = fk.get_max_value(wt, val, capacity)
print("greedy fractional knapsack")
print("maximum value: ", max_value)
The listing implements the fractional-knapsack strategy by sorting items by a value-to-weight heuristic and filling the available capacity. section 4.2.2
