Knapsack Problem/Python: Difference between revisions
m
Fixed syntax highlighting.
m (Fixed syntax highlighting.) |
|||
Line 3:
===Simple Brute-Force Solution===
<
def __init__(self, value, weight, volume):
self.value, self.weight, self.volume = value, weight, volume
Line 35:
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===
Line 41:
This handles a varying number of items
<
from collections import namedtuple
Line 86:
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
Line 97:
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
Line 181:
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
| |||