# Knapsack Problem/Python

Knapsack Problem/Python is part of Knapsack Problem. You may find other members of Knapsack Problem at Category:Knapsack Problem.

### Simple Brute-Force Solution

```class Bounty:
def __init__(self, value, weight, volume):
self.value, self.weight, self.volume = value, weight, volume

panacea = Bounty(3000,  0.3, 0.025)
ichor =   Bounty(1800,  0.2, 0.015)
gold =    Bounty(2500,  2.0, 0.002)
sack =    Bounty(   0, 25.0, 0.25)
best =    Bounty(   0,    0, 0)
current = Bounty(   0,    0, 0)

best_amounts = (0, 0, 0)

max_panacea = int(min(sack.weight // panacea.weight, sack.volume // panacea.volume))
max_ichor   = int(min(sack.weight // ichor.weight,   sack.volume // ichor.volume))
max_gold    = int(min(sack.weight // gold.weight,    sack.volume // gold.volume))

for npanacea in xrange(max_panacea):
for nichor in xrange(max_ichor):
for ngold in xrange(max_gold):
current.value = npanacea * panacea.value + nichor * ichor.value + ngold * gold.value
current.weight = npanacea * panacea.weight + nichor * ichor.weight + ngold * gold.weight
current.volume = npanacea * panacea.volume + nichor * ichor.volume + ngold * gold.volume

if current.value > best.value and current.weight <= sack.weight and \
current.volume <= sack.volume:
best = Bounty(current.value, current.weight, current.volume)
best_amounts = (npanacea, nichor, ngold)

print "Maximum value achievable is", best.value
print "This is achieved by carrying (one solution) %d panacea, %d ichor and %d gold" % \
(best_amounts[0], best_amounts[1], best_amounts[2])
print "The weight to carry is %4.1f and the volume used is %5.3f" % (best.weight, best.volume)
```

### General Brute-Force Solution

Requires Python V.2.6+

This handles a varying number of items

```from itertools import product, izip
from collections import namedtuple

Bounty = namedtuple('Bounty', 'name value weight volume')

sack =   Bounty('sack',       0, 25.0, 0.25)

items = [Bounty('panacea', 3000,  0.3, 0.025),
Bounty('ichor',   1800,  0.2, 0.015),
Bounty('gold',    2500,  2.0, 0.002)]

def tot_value(items_count):
"""
Given the count of each item in the sack return -1 if they can't be carried or their total value.

(also return the negative of the weight and the volume so taking the max of a series of return
values will minimise the weight if values tie, and minimise the volume if values and weights tie).
"""
global items, sack
weight = sum(n * item.weight for n, item in izip(items_count, items))
volume = sum(n * item.volume for n, item in izip(items_count, items))
if weight <= sack.weight and volume <= sack.volume:
return sum(n * item.value for n, item in izip(items_count, items)), -weight, -volume
else:
return -1, 0, 0

def knapsack():
global items, sack
# find max of any one item
max1 = [min(int(sack.weight // item.weight), int(sack.volume // item.volume)) for item in items]

# Try all combinations of bounty items from 0 up to max1
return max(product(*[xrange(n + 1) for n in max1]), key=tot_value)

max_items = knapsack()
maxvalue, max_weight, max_volume = tot_value(max_items)
max_weight = -max_weight
max_volume = -max_volume

print "The maximum value achievable (by exhaustive search) is %g." % maxvalue
item_names = ", ".join(item.name for item in items)
print "  The number of %s items to achieve this is: %s, respectively." % (item_names, max_items)
print "  The weight to carry is %.3g, and the volume used is %.3g." % (max_weight, max_volume)
```

Sample output

```The maximum value achievable (by exhaustive search) is 54500
The number of panacea, ichor, gold items to achieve this is: (9, 0, 11), respectively
The weight to carry is 24.7, and the volume used is 0.247```

### Specific Dynamic Programming solution

A dynamic programming approach using a 2-dimensional table (One dimension for weight and one for volume). Because this approach requires that all weights and volumes be integer, I multiplied the weights and volumes by enough to make them integer. This algorithm takes O(w*v) space and O(w*v*n) time, where w = weight of sack, v = volume of sack, n = number of types of items. To solve this specific problem it's much slower than the brute force solution.

```from itertools import product, izip
from collections import namedtuple

Bounty = namedtuple('Bounty', 'name value weight volume')

# "namedtuple" is only available in Python 2.6+; for earlier versions use this instead:
# class Bounty:
#     def __init__(self, name, value, weight, volume):
#         self.name = name
#         self.value = value
#         self.weight = weight
#         self.volume = volume

sack =   Bounty('sack',       0, 250, 250)

items = [Bounty('panacea', 3000,   3,  25),
Bounty('ichor',   1800,   2,  15),
Bounty('gold',    2500,  20,   2)]

def tot_value(items_count, items, sack):
"""
Given the count of each item in the sack return -1 if they can't be carried or their total value.

(also return the negative of the weight and the volume so taking the max of a series of return
values will minimise the weight if values tie, and minimise the volume if values and weights tie).
"""
weight = sum(n * item.weight for n, item in izip(items_count, items))
volume = sum(n * item.volume for n, item in izip(items_count, items))
if weight <= sack.weight and volume <= sack.volume:
return sum(n * item.value for n, item in izip(items_count, items)), -weight, -volume
else:
return -1, 0, 0

def knapsack_dp(items, sack):
"""
Solves the Knapsack problem, with two sets of weights,
using a dynamic programming approach
"""
# (weight+1) x (volume+1) table
# table[w][v] is the maximum value that can be achieved
# with a sack of weight w and volume v.
# They all start out as 0 (empty sack)
table = [[0] * (sack.volume + 1) for i in xrange(sack.weight + 1)]

for w in xrange(sack.weight + 1):
for v in xrange(sack.volume + 1):
# Consider the optimal solution, and consider the "last item" added
# to the sack. Removing this item must produce an optimal solution
# to the subproblem with the sack's weight and volume reduced by that
# of the item. So we search through all possible "last items":
for item in items:
# Only consider items that would fit:
if w >= item.weight and v >= item.volume:
table[w][v] = max(table[w][v],
# Optimal solution to subproblem + value of item:
table[w - item.weight][v - item.volume] + item.value)

# Backtrack through matrix to re-construct optimum:
result = [0] * len(items)
w = sack.weight
v = sack.volume
while table[w][v]:
# Find the last item that was added:
aux = [table[w-item.weight][v-item.volume] + item.value for item in items]
i = aux.index(table[w][v])

# Record it in the result, and remove it:
result[i] += 1
w -= items[i].weight
v -= items[i].volume

return result

max_items = knapsack_dp(items, sack)
max_value, max_weight, max_volume = tot_value(max_items, items, sack)
max_weight = -max_weight
max_volume = -max_volume

print "The maximum value achievable (by exhaustive search) is %g." % max_value
item_names = ", ".join(item.name for item in items)
print "  The number of %s items to achieve this is: %s, respectively." % (item_names, max_items)
print "  The weight to carry is %.3g, and the volume used is %.3g." % (max_weight, max_volume)
```

Sample output

```The maximum value achievable (by dynamic programming) is 54500
The number of panacea,ichor,gold items to achieve this is: [9, 0, 11], respectively
The weight to carry is 247, and the volume used is 247```