Knapsack Problem/Python: Difference between revisions

{{collection|Knapsack Problem}}

 

 

def __init__(self, value, weight, volume):

self.value, self.weight, self.volume = value, weight, volume

print "This is achieved by carrying (one solution) %d panacea, %d ichor and %d gold" % \

(best_amounts[0], best_amounts[1], best_amounts[2])

 

Requires Python V.2.6+

from collections import namedtuple

 

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)

 

Sample output

The weight to carry is 24.7, and the volume used is 0.247</pre>

 

 

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 collections import namedtuple

 

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)

 

Sample output

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</pre>