Algorithms greedy

Summary

A greedy algorithm optimizes locally at each pass involved in a function.
Trading off accuracy to exit earlier.

https://upload.wikimedia.org/wikipedia/commons/8/8c/Greedy-search-path-example.gif

Knapsack Problem

You are a burglar and want to fill your moneybag with the maximum total value.

- A knapsack has a max weight
- Items have a weight, and a value

It is impossible to calculate this precisely without
creating a list of every posible combination and comparing them.

Instead, we'll sort our items by value,
and add add items to the bag starting with the most valuable until the bag is full.

from collections import namedtuple
from functools import reduce

Item = namedtuple('item', ['weight', 'value'])

items = [Item(weight=1, value=10),
         Item(weight=10, value=3),
         Item(weight=6, value=8)]

def pack_bag(weight_capacity, items):
    pack_items = []
    items_by_weight_desc = sorted(items, key=lambda i: i.weight, reverse=True)

    for item in items_by_weight_desc:
        pack_weight = reduce(lambda agg, i: agg + i.weight, lambdapack_items)
        if pack_weight + item.weight <= weight_capacity:
            pack_items.append(item)
        else:
            return pack_items