Динамическое программирование

import itertools
from itertools import product, zip_longest
from collections import namedtuple
 
Goods = namedtuple('Goods', '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 =   Goods('sack',       0, 8000, 32)
 
items = [Goods('1', 108000,   3000,  5),
         Goods('2',   60000,   1300,  2),
         Goods('3',    9000,  2100,   4),
         Goods('4',   102000,   1900,  3),
         Goods('5',   118000,   2600,  5),
         Goods('6',   30000,   300,  1)]
 
 
table = [[0] * (sack.volume + 1) for i in range(sack.weight + 1)]
 
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)
    
 
    for w in range(sack.weight+1):
        for v in range(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 = w - items[i].weight
        v = 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))