I'm working on modernizing Rosetta Code's infrastructure. Starting with communications. Please accept this time-limited open invite to RC's Slack.. --Michael Mol (talk) 20:59, 30 May 2020 (UTC)

# 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.valueprint "This is achieved by carrying (one solution) %d panacea, %d ichor and %d gold" % \       (best_amounts, best_amounts, best_amounts)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, izipfrom 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_weightmax_volume = -max_volume print "The maximum value achievable (by exhaustive search) is %g." % maxvalueitem_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, izipfrom 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 = [ * (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 =  * 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_weightmax_volume = -max_volume print "The maximum value achievable (by exhaustive search) is %g." % max_valueitem_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```