# Knapsack Problem (0-1 solution) – Dynamic Algorithm

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 dynamic algorithm.

```# Math is used to floor/round the floats to an interger and back!
import math
# Total allowed weight
totalWeight = 2392;

# Define the items name, Weight, Profit
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),
("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))

# Get the total of bagged items.
def totalvalue(comb):
totwt = totval = 0
for item, wt, val in comb:
totwt  += wt
totval += val
return (totval, -totwt) if totwt <= totalWeight else (0, 0)

# The knapsack 0-1 Dynamic Programming Algorithm.
def knapsack(items, limit):
table = [[0 for w in range(limit + 1)] for j in xrange(len(items) + 1)]

for j in xrange(1, len(items) + 1):
item, wt, val = items[j-1]
wt = int(wt * 100)
val = int(val * 100)
for w in xrange(1, limit + 1):
if wt > w:
table[j][w] = table[j-1][w]
else:
table[j][w] = max(table[j-1][w],
table[j-1][w-wt] + val)

result = []
w = limit
for j in range(len(items), 0, -1):
was_added = table[j][w] != table[j-1][w]

item, wt, val = items[j-1]
wt = int(wt * 100)
val = int(val * 100)
result.append(items[j-1])
w -= wt

return result

# Bag the items
bagged = knapsack(items, totalWeight)

# Print the results
print("Bagged the following items\n  " +
'\n  '.join(sorted(item for item,_,_ in bagged)))
val, wt = totalvalue(bagged)

print("Total Value: %f - Total Weight: %f" % (float(val), float(-wt)))```

Posted in code