I’ve recently dug up old code from my University days, which I thought I’d share for the benefit/misfortune of others.

There’s a common problem in programming called the knapsack problem. Here was my solution based on the greedy algorithm.

# Name, Weight and Value of Items
items = [("Weapon and Ammunition",    4.13, 1.4),
         ("Water", 2.13, 2.74),
         ("Pith Helmet", 3.03, 1.55),
         ("Sun Cream", 2.26, 0.82),
         ("Tent", 3.69, 2.38),
         ("Flare Gun", 3.45, 2.93),
         ("Olive Oil", 1.09, 1.77),
         ("Firewood", 2.89, 0.53),
         ("Kendal Mint Cake", 1.08, 2.77),
         ("Snake Repellant Spray", 3.23, 4.29),
         ("Bread", 2.29, 2.85),
         ("Pot Noodles", 0.55, 0.34),
         ("Software Engineering Textbook", 2.82, -0.45),
         ("Tinned Food", 2.31, 2.17),
         ("Pork Pie", 1.63, 1.62)]

# Maximum Weight Allowed.
MAXIMUM = 15.0

# Sort items based on effeciency (value/weight).
sorted_items = sorted(((value/amount, amount, name)
                       for name, amount, value in items),
                      reverse = True)

# Define the total weight and value.
wt = val = 0
# Define an array for the items which are bagged.
bagged = []

# Loop through the item array and bag items until full
for unit_value, amount, name in sorted_items:
    weight = min(MAXIMUM - wt, amount)
    wt     += weight
    addval  = weight * unit_value
    val    += addval
    bagged += [(name, weight, addval)]
    if wt >= MAXIMUM:
        break

# Print results!
print("    ITEM   WEIGHT  VALUE")
print("\n".join("%10s %6.2f %6.2f" % item for item in bagged))
print("\nTotal Bagged Weight: %5.2f\nTotal Bagged Value: %5.2f" % (wt, val))